LLVM-Loop-Simple-Introduction

Quesitons before read

来源:LoopTerminology

主要问题需要弄明白：

• loop’s definition and properties
  • a subset strong connected
  • maximu subset
  • ….
    • loop is structured,known
  • some attribuete mustprogress….
• loop’s terminology
  • preheader
  • entering block
  • exit block
  • exiting block
  • backdge
• irreducible control-flow
  • how to convert it?
• loop trip count
  • back-edge count
• LoopInfo,difference between structured loops and arbitrary cycles
• simplify form‘s properties and advantanged
  • loop latch,loop header,dedicated exits
  • ir sample and cp sample
  • why to converted to simplify form
    • control-flow analysis, so better data analysis
• LCSSA
  • lcssa is for data anlaysis
• loop rotate
  • what loop rotate will do, what will be changed.
  • ensure canonical form
  • advantanges?

LLVM Loop Terminology (and Canonical Forms)

Loop Definition

Loops are an important concept for a code optimizer. In LLVM, detection of loops in a control-flow graph is done by LoopInfo. It is based on the following definition. A loop is a subset of nodes from the control-flow graph (CFG; where nodes represent basic blocks) with the following properties:

loop是代码优化器的一个重要概念。在LLVM中，控制流图中的loop检测是由LoopInfo完成的。它基于以下定义。

Loop是控制流图(CFG;其中节点表示基本块)具有以下属性:

1. The induced subgraph (which is the subgraph that contains all the edges from the CFG within the loop) is strongly connected (every node is reachable from all others).

2. All edges from outside the subset into the subset point to the same node, called the header. As a consequence, the header dominates all nodes in the loop (i.e. every execution path to any of the loop’s node will have to pass through the header).

3. The loop is the maximum subset with these properties. That is, no additional nodes from the CFG can be added such that the induced subgraph would still be strongly connected and the header would remain the same.

   诱导子图(包含环路中CFG的所有边的子图)是强连接的(每个节点都可以从所有其他节点到达)

   所有从子集外部进入子集的边都指向同一个节点，称为header。因此，header dominates loop中的所有节点(即，到任何loop节点的每个执行路径都必须经过header).

   Loop是具有这些属性的最大子集。也就是说，不能添加来自CFG的额外节点，这样诱导子图仍然是强连接的，并且header将保持不变.

   但是思考一个问题,subset loop是最大子集吗？

In computer science literature, this is often called a natural loop. In LLVM, a more generalized definition is called a cycle.

Terminology

The definition of a loop comes with some additional terminology:

loop的定义有一些额外的术语:

• An entering block (or loop predecessor) is a non-loop node that has an edge into the loop (necessarily the header). If there is only one entering block, and its only edge is to the header, it is also called the loop’s preheader. The preheader dominates the loop without itself being part of the loop.

进入块(或loop前身)是一个非loop节点，它具有进入loop的边(必须是header)。如果只有一个进入块，并且它的唯一edge是into header，则它也称为loop的preheader。preheader dominates loop，但它本身不是loop的一部分。

注意header 和pre header不同，一个in loop，一个out of loop.

• A latch is a loop node that has an edge to the header.
• A backedge is an edge from a latch to the header.
• An exiting edge is an edge from inside the loop to a node outside of the loop. The source of such an edge is called an exiting block, its target is an exit block.

注意ExitingBlock和ExitBlock的区别

Important Notes

This loop definition has some noteworthy consequences:

这个loop定义有一些值得注意的结果:

A node can be the header of at most one loop. As such, a loop can be identified by its header. Due to the header being the only entry into a loop, it can be called a Single-Entry-Multiple-Exits (SEME) region.

一个节点最多只能是一个loop的header。因此，loop可以通过其header来识别。由于header是进入loop的唯一入口，因此可以称为Single-Entry-Multiple-Exits (SEME)区域。

For basic blocks that are not reachable from the function’s entry, the concept of loops is undefined. This follows from the concept of dominance being undefined as well.

对于无法从function entry访问的基本块，Loop的概念是未定义的。这也是dominance概念未定义的结果。也就是需要是reachable的

The smallest loop consists of a single basic block that branches to itself. In this case that block is the header, latch (and exiting block if it has another edge to a different block) at the same time. A single block that has no branch to itself is not considered a loop, even though it is trivially strongly connected.

最小的loop由一个branches到自身的basic block组成。在这种情况下，该块同时是header、latch (如果它有另一条通往不同块的边，则为exiting block)。没有branch的单个blcok不被认为是loop，即使它是简单的强连接。

In this case, the role of header, exiting block and latch fall to the same node. LoopInfo reports this as:

在这种情况下，header、exiting block和latch的作用落在同一个节点上。LoopInfo report如下:

$ opt input.ll -passes='print<loops>'
Loop at depth 1 containing: %for.body<header><latch><exiting>

Loops can be nested inside each other. That is, a loop’s node set can be a subset of another loop with a different loop header. The loop hierarchy in a function forms a forest: Each top-level loop is the root of the tree of the loops nested inside it.

Loop可以彼此嵌套。也就是说，loop的node set可以是具有不同loop头的另一个loop的subset。函数中的loop层次结构形成了一个forest:每个top-level loop都是嵌套在其中的loop tree的root。

It is not possible that two loops share only a few of their nodes. Two loops are either disjoint or one is nested inside the other. In the example below the left and right subsets both violate the maximality condition. Only the merge of both sets is considered a loop.

两个Loop不可能只共享它们的几个节点。两个loop要么不相交，要么一个嵌套在另一个里面。在下面的示例中，左子集和右子集都违反 maximality condition。只有两个集合的merge 才被认为是loop。(依据：The loop is the maximum subset with these properties.)

It is also possible that two logical loops share a header, but are considered a single loop by LLVM:

也有可能两个logical loops共享一个header，但被LLVM视为single loop:

for (int i = 0; i < 128; ++i)
  for (int j = 0; j < 128; ++j)
    body(i,j);

which might be represented in LLVM-IR as follows. Note that there is only a single header and hence just a single loop.

可以在LLVM-IR中表示如下。注意，只有一个header，因此只有一个loop

这也就是前面讲到nested loop时，看上去是有两个loop的，但是在llvm表示中只会是一个loop.

The LoopSimplify pass will detect the loop and ensure separate headers for the outer and inner loop.

LoopSimplify pass将检测loop，并确保外部和内部loop的头是分开的。

注意这个里面LoopSimplify是为了:

every loop has a preheader block (a single-entry, single-exit block that branches unconditionally to the loop header), and that the loop only has one exit block.

这个里面按照llvm的loop定义是只有一个:header和for.outer.

具体可以参看LoopSimilify Chapter.

A cycle in the CFG does not imply there is a loop. The example below shows such a CFG, where there is no header node that dominates all other nodes in the cycle. This is called irreducible control-flow.

CFG中的cycle并不意味着存在一个cycle。下面的示例显示了这样一个CFG，其中没有dominates loop中所有其他节点的header。这被称为不可约控制流。

下面的b->entry不是强连接的，所以一定不在loop中，loop中只有b,a.

The term reducible results from the ability to collapse the CFG into a single node by successively replacing one of three base structures with a single node: A sequential execution of basic blocks, acyclic conditional branches (or switches), and a basic block looping on itself. Wikipedia has a more formal definition, which basically says that every cycle has a dominating header.

“reducible”一词源于这样一种能力，即通过用a single node依次替换三个基本结构中的一个，将CFG压缩为single node:basic block的顺序执行、无loop条件分支(或开关)和在自身上loop的基本块。维基百科有一个更正式的定义，基本上说每个loop都有一个dominating header。

• Irreducible control-flow can occur at any level of the loop nesting. That is, a loop that itself does not contain any loops can still have cyclic control flow in its body; a loop that is not nested inside another loop can still be part of an outer cycle; and there can be additional cycles between any two loops where one is contained in the other. However, an LLVM cycle covers both, loops and irreducible control flow.

  不可约控制流可以发生在loop嵌套的任何级别。也就是说，一个Loop本身不包含任何Loop，它的主体中仍然可以有cyclic control flow;没有嵌套在另一个loop中的loop仍然可以是外部loop的一部分;在任何两个loop之间都可以有额外的loop其中一个包含在另一个中。然而，LLVM cycle包括loops和irreducible control flow.

• The FixIrreducible pass can transform irreducible control flow into loops by inserting new loop headers. It is not inlcuded in any default optimization pass pipeline, but is required for some back-end targets.

  FixIrreducible Pass可以通过插入新的loop头将不可简化的控制流转换为Loop。它不包含在任何默认的optimization pass pipeline中，但对于某些后端目标是必需的。

• Exiting edges are not the only way to break out of a loop. Other possibilities are unreachable terminators, [[noreturn]] functions, exceptions, signals, and your computer’s power button.

  退出边并不是跳出loop的唯一方法。其他可能包括不可达终止符、[[noreturn]]函数、异常、信号和计算机的电源按钮。

• A basic block “inside” the loop that does not have a path back to the loop (i.e. to a latch or header) is not considered part of the loop. This is illustrated by the following code.

  在loop内部的基本块，如果没有返回loop的路径(即到latch或headcer)，则不被认为是loop的一部分。下面的代码说明了这一点。

  下面的c1 c2 对应的block, c3对应的block,c4对应的block都不是loop的一部分.

for (unsigned i = 0; i <= n; ++i) {
  if (c1) {
    // When reaching this block, we will have exited the loop.
    do_something();
    break;
  }
  if (c2) {
    // abort(), never returns, so we have exited the loop.
    abort();
  }
  if (c3) {
    // The unreachable allows the compiler to assume that this will not rejoin the loop.
    do_something();
    __builtin_unreachable();
  }
  if (c4) {
    // This statically infinite loop is not nested because control-flow will not continue with the for-loop.
    while(true) {
      do_something();
    }
  }
}

• There is no requirement for the control flow to eventually leave the loop, i.e. a loop can be infinite. A statically infinite loop is a loop that has no exiting edges. A dynamically infinite loop has exiting edges, but it is possible to be never taken. This may happen only under some circumstances, such as when n == UINT_MAX in the code below.

  不要求控制流最终离开loop，即loop可以是无限的。静态无限loop是没有退出边的loop。动态无限loop具有退出边，但它可能永远不会被取走。这可能只在某些情况下发生，比如下面代码中的n == UINT_MAX。

for (unsigned i = 0; i <= n; ++i)
  body(i);

It is possible for the optimizer to turn a dynamically infinite loop into a statically infinite loop, for instance when it can prove that the exiting condition is always false. Because the exiting edge is never taken, the optimizer can change the conditional branch into an unconditional one.

优化器有可能将动态无限loop转换为静态无限loop，例如，当它可以证明现有条件始终为假时。因为退出的边永远不会被taken，所以optimizer可以将条件分支更改为无条件分支。

If a is loop is annotated with llvm.loop.mustprogress metadata, the compiler is allowed to assume that it will eventually terminate, even if it cannot prove it. For instance, it may remove a mustprogress-loop that does not have any side-effect in its body even though the program could be stuck in that loop forever. Languages such as C and C++ have such forward-progress guarantees for some loops. Also see the mustprogress and willreturn function attributes, as well as the older llvm.sideeffect intrinsic.

如果使用llvm.loop.mustprogress元数据注释isloop，则允许编译器假设它最终将终止，即使它无法证明这一点。例如，它可以删除一个在其体内没有任何副作用的mustprogress-loop，即使程序可能永远卡在该loop中。像C和c++这样的语言对于某些loop有这样的forward-progress保证。还可以查看mustprogress和willreturn函数属性，以及旧的llvm.sideeffect intrinsic。

例如对于下面的loop:

void endless_loop() __attribute__((noinline)) {
    [[clang::loop_optimize("llvm.loop.mustprogress")]]
    while (true) {
        // This loop doesn't have any side effects
    }
}

处理后的llvm ir如下:

define void @_Z12endless_loopv() {
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  ; ... potentially other loop related metadata ...
  !llvm.loop.mustprogress = !{!0}
  br label %loop
}

!0 = !{}

如果LLVM在优化过程中尊重llvm.loop.mustprogress metadata（并且根据您所描述的语义），那么优化后的IR可以完全消除loop，因为该loop没有副作用:

define void @_Z12endless_loopv() {
entry:
  ret void
}

• The number of executions of the loop header before leaving the loop is the loop trip count (or iteration count). If the loop should not be executed at all, a loop guard must skip the entire loop:

  在离开loop之前执行loop头的次数是loop行程计数(或迭代计数)。如果根本不应该执行loop，则loop guard必须跳过整个loop:

Since the first thing a loop header might do is to check whether there is another execution and if not, immediately exit without doing any work (also see Rotated Loops), loop trip count is not the best measure of a loop’s number of iterations. For instance, the number of header executions of the code below for a non-positive n (before loop rotation) is 1, even though the loop body is not executed at all.

由于loop头可能要做的第一件事情是检查是否有另一个执行，如果没有，则立即退出而不执行任何工作（也请参见Rotateloops），因此loop迭代次数并不是衡量loop迭代次数的最佳指标。例如，对于非正n（在LoopRotate之前），下面代码的header执行次数为1，即使根本没有执行loop体。

for (int i = 0; i < n; ++i)
  body(i);

A better measure is the **backedge-taken count, which is the number of times any of the backedges is taken before the loop. It is one less than the trip count for executions that enter the header.

更好的度量方法是backendge -taken count，这是在loop之前任何back edge被执行的次数。它比进入header的执行的trip count少一次

LoopInfo

LoopInfo is the core analysis for obtaining information about loops. There are few key implications of the definitions given above which are important for working successfully with this interface. LoopInfo does not contain information about non-loop cycles. As a result, it is not suitable for any algorithm which requires complete cycle detection for correctness. LoopInfo provides an interface for enumerating all top level loops (e.g. those not contained in any other loop). From there, you may walk the tree of sub-loops rooted in that top level loop. Loops which become statically unreachable during optimization must be removed from LoopInfo. If this can not be done for some reason, then the optimization is required to preserve the static reachability of the loop.

LoopInfo是获取loop information的核心分析。上面给出的定义有几个关键的含义，这些含义对于成功地使用这个接口很重要。

LoopInfo不包含non-loop cycles的信息。因此，它不适用于任何需要complete cycle检测正确性的算法。

LoopInfo提供了一个接口来枚举所有top level loops(例如那些不包含在任何其他loop中的loop)。从那里，您可以遍历植根于top level loops的sub-loops。

在优化过程中变得静态不可达的loop必须从LoopInfo中删除。如果由于某种原因不能做到这一点，则需要进行优化以保持loop的静态可达性。

“structured loops”指的是有明确入口点、loop body和决定循环是否继续或退出的条件等特征，可以被识别为for、while或do-while等传统编程语言中的循环结构。而“arbitrary cycles”则指控制流图中任意形成的闭合路径，不一定符合传统编程语言中定义的循环结构(例如goto)。

Loop Simplify Form

The Loop Simplify Form is a canonical form that makes several analyses and transformations simpler and more effective. It is ensured by the LoopSimplify (-loop-simplify) pass and is automatically added by the pass managers when scheduling a LoopPass. This pass is implemented in LoopSimplify.h. When it is successful, the loop has:

loop简化形式是一种规范的形式，它使一些分析和转换更简单、更有效。它由LoopSimplify (-loop-simplify)通道确保，并且在调度LoopPass时由pass manager自动添加。此传递在LoopSimplify.h中实现。当它成功时，loop有:

• A preheader.
• A single backedge (which implies that there is a single latch).
• Dedicated exits. That is, no exit block for the loop has a predecessor that is outside the loop. This implies that all exit blocks are dominated by the loop header.

Dedicated exits专门的出口。也就是说，loop的exit block在loop之外没有predecessor.这意味着所有exit block都由loop头控制

Dedicated exits

define void @func() {
entry:
  br label %loop.header

loop.header:
  %cond = icmp slt i32 %i, 10
  br i1 %cond, label %loop.body, label %loop.exit

loop.body:
  ; Some code here...
  br i1 %someCondition, label %loop.exit, label %loop.header

outside:
  ; Some code that's outside the loop but still branches to loop.exit
  br label %loop.exit

loop.exit:
  ; This block is the exit block for the loop and has predecessors both from inside and outside the loop.
  ret void
}

参照下面的cpp code来看详细的步骤:

bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                   MemorySSAUpdater *MSSAU,
                                   bool PreserveLCSSA) {
  bool Changed = false;

  // We re-use a vector for the in-loop predecesosrs.
  SmallVector<BasicBlock *, 4> InLoopPredecessors;

  auto RewriteExit = [&](BasicBlock *BB) {
    assert(InLoopPredecessors.empty() &&
           "Must start with an empty predecessors list!");
    auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });

    // See if there are any non-loop predecessors of this exit block and
    // keep track of the in-loop predecessors.
    bool IsDedicatedExit = true;
    for (auto *PredBB : predecessors(BB))
      if (L->contains(PredBB)) {
        if (isa<IndirectBrInst>(PredBB->getTerminator()))
          // We cannot rewrite exiting edges from an indirectbr.
          return false;

        InLoopPredecessors.push_back(PredBB);
      } else {
        IsDedicatedExit = false;
      }

    assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");

    // Nothing to do if this is already a dedicated exit.
    if (IsDedicatedExit)
      return false;

    auto *NewExitBB = SplitBlockPredecessors(
        BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);

    if (!NewExitBB)
      LLVM_DEBUG(
          dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
                 << *L << "\n");
    else
      LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
                        << NewExitBB->getName() << "\n");
    return true;
  };

  // Walk the exit blocks directly rather than building up a data structure for
  // them, but only visit each one once.
  SmallPtrSet<BasicBlock *, 4> Visited;
  for (auto *BB : L->blocks())
    for (auto *SuccBB : successors(BB)) {
      // We're looking for exit blocks so skip in-loop successors.
      if (L->contains(SuccBB))
        continue;

      // Visit each exit block exactly once.
      if (!Visited.insert(SuccBB).second)
        continue;

      Changed |= RewriteExit(SuccBB);
    }

  return Changed;
}

1. 找到所有不在Loop中的successor，也就是loop.exit，它对应有三个predecessors:”loop.header”, “loop.body”, “outside”.
2. InLoopPredecessors为： “loop.header”,”loop.body”
3. 由于找到了一个dedicate exit也就是outside,所以IsDedicatedExit=False.
4. 针对InLoopPredecessors 创建一个它们的exit：dedicated.loop.exit。
5. Finshied

最后的llvm ir就是:

define void @func() {
entry:
  br label %loop.header

loop.header:
  %cond = icmp slt i32 %i, 10
  br i1 %cond, label %loop.body, label %dedicated.loop.exit

loop.body:
  ; Some code here...
  br i1 %someCondition, label %dedicated.loop.exit, label %loop.header

outside:
  ; Some code that's outside the loop but still branches to loop.exit
  br label %loop.exit

dedicated.loop.exit:
  ; Dedicated exit block just for the loop
  br label %loop.exit

loop.exit:
  ; Now, this block only has predecessors from dedicated.loop.exit and outside
  ret void
}

A single backedge

以如下的llvm ir为例子:

define void @func() {
entry:
  br label %loop.header

loop.header:
  %cond1 = icmp slt i32 %i, 10
  br i1 %cond1, label %loop.body1, label %loop.exit

loop.body1:
  ; Some code...
  br i1 %someCondition1, label %loop.header, label %loop.body2

loop.body2:
  ; Some more code...
  br i1 %someCondition2, label %loop.header, label %loop.exit

loop.exit:
  ret void
}

这个里面有两个backedge，也就是loop.body1和loop.body2, 思路其实是同样的，给loop.body1,loop.body2创建一个相同的successor loop.merge，这样就可以只有一个loop latch: loop.merge: 最后得到的ir就是:

define void @func() {
entry:
  br label %loop.header

loop.header:
  %cond1 = icmp slt i32 %i, 10
  br i1 %cond1, label %loop.body1, label %loop.exit

loop.body1:
  ; Some code...
  br i1 %someCondition1, label %loop.merge, label %loop.body2

loop.body2:
  ; Some more code...
  br i1 %someCondition2, label %loop.merge, label %loop.exit

loop.merge:
  br label %loop.header

loop.exit:
  ret void
}

注意转变之后，loop.body1,loop.body2有返回到loop latch的edge，所以它们仍然是loop的一部分.

上面两个方式都是通过split,merge block完成的.

advantages

• 更少的控制流路径, 促进数据依赖分析：
• • 只有一个入口点和dedicated exits(和loop 外部无关)
• • • 外部需要考虑loop的指令流程复杂度降低
• • • …
• • a single latch(single back edge)，single back edge 意味着single cycle
• • • 确保了重新进入loop地确定性.
• • • 更好确定loop地trip count.
• • • 例如如果是loop unroll的话，只需要unroll single back edge 对应的cycle就行

实际的例子，比如促进loop-invariant code移动：通过清晰地定义前置条件，更容易将不变量代码（无论loop迭代多少次都不会改变的代码）从loop中移出，这是一种常见优化。

Loop Closed SSA (LCSSA)

A program is in Loop Closed SSA Form if it is in SSA form and all values that are defined in a loop are used only inside this loop. Programs written in LLVM IR are always in SSA form but not necessarily in LCSSA. To achieve the latter, for each value that is live across the loop boundary, single entry PHI nodes are inserted to each of the exit blocks [1] in order to “close” these values inside the loop. In particular, consider the following loop:

如果程序处于Loop closed SSA形式，并且在loop中定义的所有值仅在该loop中使用，则该程序处于loop封闭SSA形式。 用LLVM IR编写的程序总是采用SSA形式，但不一定采用LCSSA形式。为了实现后者，对于每个在loop边界上存在的值，将single entry PHI节点插入到每个exit blocks[1]中，以便在loop内“close”这些值。具体来说，考虑下面的loop:

c = ...;
for (...) {
  if (c)
    X1 = ...
  else
    X2 = ...
  X3 = phi(X1, X2);  // X3 defined
}

... = X3 + 4;  // X3 used, i.e. live
               // outside the loop

In the inner loop, the X3 is defined inside the loop, but used outside of it. In Loop Closed SSA form, this would be represented as follows:

在内部loop中，X3在loop内部定义，但在loop外部使用。在Loop Closed SSA形式中，这将表示为:

c = ...;
for (...) {
  if (c)
    X1 = ...
  else
    X2 = ...
  X3 = phi(X1, X2);
}
X4 = phi(X3);

... = X4 + 4;

This is still valid LLVM; the extra phi nodes are purely redundant, but all LoopPass’es are required to preserve them. This form is ensured by the LCSSA (-lcssa) pass and is added automatically by the LoopPassManager when scheduling a LoopPass. After the loop optimizations are done, these extra phi nodes will be deleted by -instcombine.

这仍然是有效的LLVM;额外的phi节点是完全冗余的，但是所有的LoopPass都需要保留它们。此表单由LCSSA (-lcssa) pass 确保，并在调度LoopPass时由LoopPassManager自动添加。在Loop optimization完成后，这些额外的phi节点将通过-instcombine删除。

Note that an exit block is outside of a loop, so how can such a phi “close” the value inside the loop since it uses it outside of it ? First of all, for phi nodes, as mentioned in the LangRef: “the use of each incoming value is deemed to occur on the edge from the corresponding predecessor block to the current block”. Now, an edge to an exit block is considered outside of the loop because if we take that edge, it leads us clearly out of the loop.

请注意，exit block位于loop之外，那么既然在loop之外使用了该值，那么如何在loop内“close”该值呢?首先，对于phi节点，正如LangRef中提到的:“每个incoming value的使用被认为发生在从对应的predecessor block到current block的edge上”。现在，exit block的edge被认为是loop 之外的，因为如果我们取走那条edge，它就会把我们带出loop。

However, an edge doesn’t actually contain any IR, so in source code, we have to choose a convention of whether the use happens in the current block or in the respective predecessor. For LCSSA’s purpose, we consider the use happens in the latter (so as to consider the use inside) .

然而，edge实际上不包含任何IR，因此在源代码中，我们必须选择一种约定，即use是发生在current block中还是在各自的predecessor中。对于LCSSA，我们认为使用发生在后者predecessor(以便考虑use inside)。

The major benefit of LCSSA is that it makes many other loop optimizations simpler. First of all, a simple observation is that if one needs to see all the outside users, they can just iterate over all the (loop closing) PHI nodes in the exit blocks (the alternative would be to scan the def-use chain [3] of all instructions in the loop).

LCSSA的主要优点是它简化了许多其他loop optimizations.

首先，一个简单的observation是，如果需要查看所有outside users，他们可以迭代exit blocks中的所有(loop closing)PHI节点(另一种选择是扫描loop中所有指令的def-use chain)。

Then, consider for example -loop-unswitch ing the loop above. Because it is in LCSSA form, we know that any value defined inside of the loop will be used either only inside the loop or in a loop closing PHI node. In this case, the only loop closing PHI node is X4. This means that we can just copy the loop and change the X4 accordingly, like so:

然后，例如，考虑-loop-unswitch上面的loop。因为它是LCSSA形式的，所以我们知道在loop内部定义的任何值将仅在loop内部或在loop结束的PHI节点中使用。在这种情况下，唯一闭合环路的PHI节点是X4。这意味着我们可以复制loop并相应地改变X4，如下所示:

c = ...;
if (c) {
  for (...) {
    if (true)
      X1 = ...
    else
      X2 = ...
    X3 = phi(X1, X2);
  }
} else {
  for (...) {
    if (false)
      X1' = ...
    else
      X2' = ...
    X3' = phi(X1', X2');
  }
}
X4 = phi(X3, X3')

Now, all uses of X4 will get the updated value (in general, if a loop is in LCSSA form, in any loop transformation, we only need to update the loop closing PHI nodes for the changes to take effect). If we did not have Loop Closed SSA form, it means that X3 could possibly be used outside the loop. So, we would have to introduce the X4 (which is the new X3) and replace all uses of X3 with that. However, we should note that because LLVM keeps a def-use chain [3] for each Value, we wouldn’t need to perform data-flow analysis to find and replace all the uses (there is even a utility function, replaceAllUsesWith(), that performs this transformation by iterating the def-use chain).

现在，X4的所有使用都将获得更新的值(通常，如果loop是LCSSA形式，在任何loop转换中，我们只需要更新loop关闭PHI节点即可使更改生效)。如果我们没有Loop Closed SSA形式，这意味着X3可以在Loop外使用。因此，我们将不得不推出X4(即新的X3)，并将X3的所有use替换为X4。 然而，我们应该注意到，因为LLVM为每个Value保留了一个def-use chain，我们不需要执行data-flow analysis来find and replace all the useds(尽管确实有一个实用函数，replaceAllUsesWith()，它通过迭代def-use chain来执行此转换)。

Another important advantage is that the behavior of all uses of an induction variable is the same. Without this, you need to distinguish the case when the variable is used outside of the loop it is defined in, for example:

另一个重要的优点是，所有使用induction variable的行为是相同的。如果没有这个，你需要区分variable在定义它的loop 外使用的情况，例如:

for (i = 0; i < 100; i++) {
  for (j = 0; j < 100; j++) {
    k = i + j;
    use(k);    // use 1
  }
  use(k);      // use 2
}

Looking from the outer loop with the normal SSA form, the first use of k is not well-behaved, while the second one is an induction variable with base 100 and step 1. Although, in practice, and in the LLVM context, such cases can be handled effectively by SCEV. Scalar Evolution (scalar-evolution) or SCEV, is a (analysis) pass that analyzes and categorizes the evolution of scalar expressions in loops.

从normal SSA形式的外loop来看，k的first use表现不佳，而第二个是一个以100为基数，步长为1的归纳变量。尽管在实践中，在LLVM上下文中，这种情况可以由SCEV有效地处理。标量演化(Scalar - Evolution)或SCEV，是一个(分析)通道，用于分析和分类loop中标量表达式的演化。

In general, it’s easier to use SCEV in loops that are in LCSSA form. The evolution of a scalar (loop-variant) expression that SCEV can analyze is, by definition, relative to a loop. An expression is represented in LLVM by an llvm::Instruction. If the expression is inside two (or more) loops (which can only happen if the loops are nested, like in the example above) and you want to get an analysis of its evolution (from SCEV), you have to also specify relative to what Loop you want it. Specifically, you have to use getSCEVAtScope().

一般来说，在LCSSA形式的loop中使用SCEV更容易。根据定义，SCEV可以分析的标量(loop变量)表达式的演变是相对于loop的。expression在LLVM中由llvm::instruction表示。如果expression在两个(或更多)loop中(只有在loop嵌套的情况下才会发生，就像上面的例子一样)，并且您想要获得其evolution的analysis(从SCEV)，您还必须指定相对于您想要的loop。具体来说，必须使用getSCEVAtScope()。

However, if all loops are in LCSSA form, each expression is actually represented by two different llvm::Instructions. One inside the loop and one outside, which is the loop-closing PHI node and represents the value of the expression after the last iteration (effectively, we break each loop-variant expression into two expressions and so, every expression is at most in one loop). You can now just use getSCEV(). and which of these two llvm::Instructions you pass to it disambiguates the context / scope / relative loop.

但是，如果所有loop都采用LCSSA形式，则每个expression实际上由两个不同的llvm::Instructions表示。一个在loop内，一个在loop外，它是结束loop的PHI节点，表示最后一次迭代后expression的值(实际上，我们将每个loop-variant expression分解为两个表达式，因此，每个表达式最多在一个loop中)。现在只需使用getSCEV()即可。以及您传递给它的这两个llvm::instruction中的哪一个消除了上下文/作用域/相对loop的歧义.

其实就是更加明确了use-def 的关系.

Simple Example for LCSSA

define void @example() {
entry:
  br label %loop.header

loop.header:
  %i = phi i32 [0, %entry], [%i.next, %loop.body]
  br label %loop.body

loop.body:
  %i.next = add i32 %i, 1
  %cond = icmp slt i32 %i.next, 5
  br i1 %cond, label %loop.header, label %loop.exit

loop.exit:
  ; Some value computed inside the loop and used outside of it
  %outside.use = mul i32 %i.next, 2
  ret void
}

在上面的例子中，%i.next是一个在loop内定义但在loop外部使用的值，具体来说是在loop.exit块中使用。 LCSSA Transformation之后,它就变成如下形式:

define void @example() {
entry:
  br label %loop.header

loop.header:
  %i = phi i32 [0, %entry], [%i.next, %loop.body]
  br label %loop.body

loop.body:
  %i.next = add i32 %i, 1
  %cond = icmp slt i32 %i.next, 5
  br i1 %cond, label %loop.header, label %loop.exit

loop.exit:
  %i.lcssa = phi i32 [%i.next, %loop.body] ; LCSSA phi node
  %outside.use = mul i32 %i.lcssa, 2
  ret void
}

现在，在loop内计算并在外部使用的任何值只能通过phi节点%i.lcssa获得。 好处：

• 更容易发现外部使用：要查找loop外使用的所有值，只需查看退出块中的phi节点即可。在我们的示例中，%i.lcssa是唯一这样的值。
• 简化loop transformation：假设您想应用某些loop转换，如Loop unroll或Loop unswitching。知道所有外部使用都被phi节点捕获使得这些transformations更加可预测和直观。

例如,如果您要分裂或复制此loop，则只需要确保phi节点%i.lcssa在每个变体中捕获正确的值，而无需跟踪% i.next 在loop之外的所有潜在用途。 个人想法是增加LCSSA form，和外部的SSA phi绑定，这样loop transformation的时候，只需要关注和LCSSA相关的code，因为外部code除了phi node是不会有LCSSA的use的，简化了处理.

“More Canonical” Loops

Rotated Loops

Loops are rotated by the LoopRotate (loop-rotate) pass, which converts loops into do/while style loops and is implemented in LoopRotation.h. Example:

loop由LoopRotate (loop-rotate)传递来旋转，它将loop转换为do/while样式的loop，并在LoopRotate.h中实现。例子:

void test(int n) {
  for (int i = 0; i < n; i += 1)
    // Loop body
}
transformed to:
void test(int n) {
  int i = 0;
  do {
    // Loop body
    i += 1;
  } while (i < n);
}

Warning: This transformation is valid only if the compiler can prove that the loop body will be executed at least once. Otherwise, it has to insert a guard which will test it at runtime. In the example above, that would be:

警告:只有当编译器能够证明loop body将至少执行一次时，此转换才有效。否则，它必须insert一个guard，在运行时对它进行测试。在上面的例子中，这将是:

void test(int n) {
  int i = 0;
  if (n > 0) {
    do {
      // Loop body
      i += 1;
    } while (i < n);
  }
}

It’s important to understand the effect of loop rotation at the LLVM IR level. We follow with the previous examples in LLVM IR while also providing a graphical representation of the control-flow graphs (CFG). You can get the same graphical results by utilizing the view-cfg pass.

在LLVM IR级别理解Loop Rotate的影响是很重要的。我们在LLVM IR中继续前面的示例，同时还提供了控制流图(CFG)的图形表示。您可以通过使用view-cfg通道获得相同的图形结果。

The initial for loop could be translated to:

define void @test(i32 %n) {
entry:
  br label %for.header

for.header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %cond = icmp slt i32 %i, %n
  br i1 %cond, label %body, label %exit

body:
  ; Loop body
  br label %latch

latch:
  %i.next = add nsw i32 %i, 1
  br label %for.header

exit:
  ret void
}

cfg图如下:

Before we explain how LoopRotate will actually transform this loop, here’s how we could convert it (by hand) to a do-while style loop.

在解释LoopRotate如何实际转换这个loop之前，先来看看如何将它(手工)转换为do-while样式的loop.

define void @test(i32 %n) {
entry:
  br label %body

body:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  ; Loop body
  br label %latch

latch:
  %i.next = add nsw i32 %i, 1
  %cond = icmp slt i32 %i.next, %n
  br i1 %cond, label %body, label %exit

exit:
  ret void
}

cfg图如下:

Note two things:

• The condition check was moved to the “bottom” of the loop, i.e. the latch. This is something that LoopRotate does by copying the header of the loop to the latch.
• The compiler in this case can’t deduce that the loop will definitely execute at least once so the above transformation is not valid. As mentioned above, a guard has to be inserted, which is something that LoopRotate will do. This is how LoopRotate transforms this loop:

  注意两点:

  • condition check移到了loop的“bottom”，即latch。这是LoopRotate通过将loop的header复制到latch来完成的。
  • 在这种情况下，compiler不能推断出loop肯定会至少执行一次，所以上面的转换是无效的。如上所述，必须插入一个guard，这是LoopRotate将要做的事情。

  下面是LoopRotate对这个loop的转换:

define void @test(i32 %n) {
entry:
  %guard_cond = icmp slt i32 0, %n
  br i1 %guard_cond, label %loop.preheader, label %exit

loop.preheader:
  br label %body

body:
  %i2 = phi i32 [ 0, %loop.preheader ], [ %i.next, %latch ]
  br label %latch

latch:
  %i.next = add nsw i32 %i2, 1
  %cond = icmp slt i32 %i.next, %n
  br i1 %cond, label %body, label %loop.exit

loop.exit:
  br label %exit

exit:
  ret void
}

对应的cfg图如下:

The result is a little bit more complicated than we may expect because LoopRotate ensures that the loop is in Loop Simplify Form after rotation. In this case, it inserted the %loop.preheader basic block so that the loop has a preheader and it introduced the %loop.exit basic block so that the loop has dedicated exits (otherwise, %exit would be jumped from both %latch and %entry, but %entry is not contained in the loop). Note that a loop has to be in Loop Simplify Form beforehand too for LoopRotate to be applied successfully.

结果比我们预期的要复杂一些，因为LoopRotate确保loop在旋转后处于loop Simplify Form。在本例中，它插入了%loop.preheader basic block，这样loop就有一个预头，它引入了%loop.exit basic block，以便loop具有dedicated exits.(否则，%exit将从%latch和%entry中跳转，但是%entry不包含在loop中)。注意，要成功应用LoopRotate，Loop也必须事先处于loop Simplify Form中。

确保一直处理LoopSimplifyForm才导致了些许复杂(多出了preheader)

The main advantage of this form is that it allows hoisting invariant instructions, especially loads, into the preheader. That could be done in non-rotated loops as well but with some disadvantages. Let’s illustrate them with an example:

这种形式的主要优点是，它允许将invariant instructions(尤其是load) hoist到preheader中。在non-rotated的loops中也可以这样做，但是有一些缺点。让我们用一个例子来说明它们:

for (int i = 0; i < n; ++i) {
  auto v = *p;
  use(v);
}

We assume that loading from p is invariant and use(v) is some statement that uses v. If we wanted to execute the load only once we could move it “out” of the loop body, resulting in this:

我们假设从p加载是不变的，而use(v)是使用v的某个语句。如果我们只想执行一次加载，我们可以将它“move out” loop body，结果如下:

auto v = *p;
for (int i = 0; i < n; ++i) {
  use(v);
}

However, now, in the case that n <= 0, in the initial form, the loop body would never execute, and so, the load would never execute. This is a problem mainly for semantic reasons. Consider the case in which n <= 0 and loading from p is invalid. In the initial program there would be no error. However, with this transformation we would introduce one, effectively breaking the initial semantics.

然而，现在，在n <= 0的情况下，在初始形式中，loop体永远不会执行，因此，加载永远不会执行。这主要是语义上的问题。考虑n <= 0且从p load无效的情况。在初始程序中不会有错误。然而，通过这个transormation，我们将引入一个，有效地打破初始语义。

To avoid both of these problems, we can insert a guard:

if (n > 0) {  // loop guard
  auto v = *p;
  for (int i = 0; i < n; ++i) {
    use(v);
  }
}

This is certainly better but it could be improved slightly. Notice that the check for whether n is bigger than 0 is executed twice (and n does not change in between). Once when we check the guard condition and once in the first execution of the loop. To avoid that, we could do an unconditional first execution and insert the loop condition in the end. This effectively means transforming the loop into a do-while loop:

这当然更好了，但还可以稍微改进一下。注意，检查n是否大于0会执行两次(其间n不会改变)。一次是在check the guard condition时，一次是在loop的first execution时。为了避免这种情况，我们可以进行unconditional first execution，并在最后插入loop condition。这实际上意味着将loop转换为do-whileloop:

if (0 < n) {
  auto v = *p;
  do {
    use(v);
    ++i;
  } while (i < n);
}

Note that LoopRotate does not generally do such hoisting. Rather, it is an enabling transformation for other passes like Loop-Invariant Code Motion (-licm).

注意，LoopRotate通常不会进行这样的提升。相反，它是支持其他传递的转换，如loop不变代码运动(-licm)。