LoopAnalysis

IRLoop，包含以下几个关键概念：

3c8be26c533e4fb694e6e05b69cf780.png

  • header: 循环的起始节点，同时也是回边指向的节点
  • entering block: 指向header的基本块，不属于循环内
  • latch: 循环内指向循环的基本块
  • exiting block: 存在一条边从exiting block指向循环外
  • exit block: exiting edge指向的基本块就是exit block, 不属于循环内

IRLoop有以下性质：

  • 一个loop的header是唯一的：也就是说一个loop可以由它的header确定，一个节点最多也只能是一个loop的header
  • loop之间可以嵌套：如一个大loop中包含一个小loop
  • 两个loop不会交叉：两个loop要么不相交，要么是嵌套关系，永远不会只共享一部分节点。如下图中的两个loop，我们会将其结合视作一个loop

42d7ef9dca7b940f103dc138d5318e2.png

LoopInfo

该部分源码地址：https://llvm.org/doxygen/GenericLoopInfoImpl_8h_source.html#l00573

LoopInfo Pass会识别IR中的循环，流程如下：

  • 后序遍历domTree，这样可以保证先找到内层的循环
  • 遍历每个基本块，如果这个基本块支配它的某个前继节点，那么该基本块为header, 其前继节点为latch,边是back edge
  • 以这个基本块为header开始找循环中的其他块以及该循环中的子循环，这部分的函数叫discoverAndMapSubloop

discoverAndMapSubloop的流程如下：

  • 首先沿着latchBlock倒着往回找到循环中的所有block。

考虑到header的性质，循环中的所有块都被header支配，如果该header的循环中存在subloop，那么它们一定在header的支配域中。由于我们采用后序遍历，因此subloop一定先于header被遍历

  • 遍历的block要么不在任何循环里，要么在一个已经发现的subloop中。对于不在任何循环中的block，我们直接将其加入当前header的loop，同时将其前继加入worklist中；对于已经在循环中的block，我们找到其最外层的subloop，然后设置嵌套关系，最后将subloop的header的前继加入worklist中。

最后完善循环嵌套关系：

  • 沿着支配树的postOrder，将每个基本块加入循环
  • 将每个基本块加入其对应的subLoop以及它所有祖先loop中，如果这个基本块是这个subloop的头部，那么说明该subloop中的所有块应该已经被遍历过了（postOrder），此时将该subLoop加入到它的父亲中，并调整其中blocks和它所拥有的subloops的顺序

其他的一些信息，如每个loop的latchBlock,ExitBlock等都可以根据上述信息辅助得出。

LCSSA