XChy's Blog

For life

0%

LLVM源码解析-Interval Analysis

Posted on Edited on In

Abstract

第一次专门写 blog 解析 LLVM 源码，最近在看鲸书学习编译优化，正好借这个系列结合 Theory 与 Practice。

Interval Analysis 是一种 Control Flow Analysis，常用作于其他优化如 LoopUnroll 的基础。

先看 Interval 类的代码，在编译理论里，Interval 一般指 Node 的集合， 集合里每个 \(Node \ne Head\) 都满足 \(Pred(Node) \subset Interval\) ：

Interval 类

1
2
3
4
5
class Interval {
  /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
  /// interval.  Also, any loops in this interval must go through the HeaderNode.
  ///
  BasicBlock *HeaderNode;

这里的 HeaderNode dominates Interval 里所有的 BasicBlock(Node)，代表了一个 Interval。

1
2
3
4
5
6
7
8
9
10

public:
inline Interval(BasicBlock *Header) : HeaderNode(Header) {
  Nodes.push_back(Header);
}

inline BasicBlock *getHeaderNode() const { return HeaderNode; }

/// Nodes - The basic blocks in this interval.
std::vector<BasicBlock*> Nodes;

构造函数和一些基本定义, Nodes 存了 Interval 里所有的 BasicBlock。

1
2
3
4
/// Successors - List of BasicBlocks that are reachable directly from nodes in
/// this interval, but are not in the interval themselves.
/// These nodes necessarily must be header nodes for other intervals.
std::vector<BasicBlock*> Successors;

Successors 是所有从Interval 里的 Node 可以直接到达的 Nodes

1
2
3
/// Predecessors - List of BasicBlocks that have this Interval's header block
/// as one of their successors.
std::vector<BasicBlock*> Predecessors;

Predecessors 则是满足 \(Head \in Succ(Node)\) 的所有 Node。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/// contains - Find out if a basic block is in this interval
inline bool contains(BasicBlock *BB) const {
  for (BasicBlock *Node : Nodes)
    if (Node == BB)
      return true;
  return false;
  // I don't want the dependency on <algorithm>
  //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
}

/// isSuccessor - find out if a basic block is a successor of this Interval
inline bool isSuccessor(BasicBlock *BB) const {
  for (BasicBlock *Successor : Successors)
    if (Successor == BB)
      return true;
  return false;
  // I don't want the dependency on <algorithm>
  //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
}

/// Equality operator.  It is only valid to compare two intervals from the
/// same partition, because of this, all we have to check is the header node
/// for equality.
inline bool operator==(const Interval &I) const {
  return HeaderNode == I.HeaderNode;
}

这些比较简单就不多说了。

Interval Partition 类

下面是关键的 IntervalPartition 和 IntervalIterator，也是算法核心:

1
2
3
4
5
6
7
class IntervalPartition : public FunctionPass {
  using IntervalMapTy = std::map<BasicBlock *, Interval *>;
  IntervalMapTy IntervalMap;

  using IntervalListTy = std::vector<Interval *>;
  Interval *RootInterval = nullptr;
  std::vector<Interval *> Intervals;

这里的存储类型也和理论一致，由一个根节点和所有节点的集合以及 BasicBlock 与 Interval 的对应(Map)构成。

1
2
3
4
5
6
7
8
9
10
11
// addIntervalToPartition - Add an interval to the internal list of intervals,
// and then add mappings from all of the basic blocks in the interval to the
// interval itself (in the IntervalMap).
void IntervalPartition::addIntervalToPartition(Interval *I) {
  Intervals.push_back(I);

  // Add mappings for all of the basic blocks in I to the IntervalPartition
  for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
       It != End; ++It)
    IntervalMap.insert(std::make_pair(*It, I));
}

这个函数就是加 Intervals,并把 BasicBlock 和其 Interval 的 Map 建立起来。

1
2
3
4
5
6
7
8
9
// updatePredecessors - Interval generation only sets the successor fields of
// the interval data structures.  After interval generation is complete,
// run through all of the intervals and propagate successor info as
// predecessor info.
void IntervalPartition::updatePredecessors(Interval *Int) {
  BasicBlock *Header = Int->getHeaderNode();
  for (BasicBlock *Successor : Int->Successors)
    getBlockInterval(Successor)->Predecessors.push_back(Header);
}

由于生成 Interval 时只更新了 Interval 的 Successors 数据，这里需要更新其对应的 Predecessors。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// IntervalPartition ctor - Build the first level interval partition for the
// specified function...
bool IntervalPartition::runOnFunction(Function &F) {
  // Pass false to intervals_begin because we take ownership of it's memory
  function_interval_iterator I = intervals_begin(&F, false);
  assert(I != intervals_end(&F) && "No intervals in function!?!?!");

  addIntervalToPartition(RootInterval = *I);

  ++I;  // After the first one...

  // Add the rest of the intervals to the partition.
  for (function_interval_iterator E = intervals_end(&F); I != E; ++I)
    addIntervalToPartition(*I);

  // Now that we know all of the successor information, propagate this to the
  // predecessors for each block.
  for (Interval *I : Intervals)
    updatePredecessors(I);
  return false;
}

这里就是一个 Interval 一个 Interval 地分解，根据算法原理我们可以知道， 当一个 Interval 更新完，可以根据其 Successors 更新其余的 Interval，最后更新 Preds 并划分整个函数。

Interval Iterator 类

1
2
3
4
5
6
7
8
template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
         class IGT = GraphTraits<Inverse<NodeTy *>>>
class IntervalIterator {
  std::vector<std::pair<Interval *, typename Interval::succ_iterator>> IntStack;
  std::set<BasicBlock *> Visited;
  OrigContainer_t *OrigContainer;
  bool IOwnMem;     // If True, delete intervals when done with them
                    // See file header for conditions of use

这是 Iterator 的数据结构，暂时不需要分析模板，这里直接把 NodeTy 换成 BasicBlock, OrigContainer 看成 Function。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// ProcessInterval - This method is used during the construction of the
// interval graph.  It walks through the source graph, recursively creating
// an interval per invocation until the entire graph is covered.  This uses
// the ProcessNode method to add all of the nodes to the interval.
//
// This method is templated because it may operate on two different source
// graphs: a basic block graph, or a preexisting interval graph.
bool ProcessInterval(NodeTy *Node) {
  BasicBlock *Header = getNodeHeader(Node);
  if (!Visited.insert(Header).second)
    return false;

  Interval *Int = new Interval(Header);

  // Check all of our successors to see if they are in the interval...
  for (typename GT::ChildIteratorType I = GT::child_begin(Node),
         E = GT::child_end(Node); I != E; ++I)
    ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));

  IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
  return true;
}

// ProcessNode - This method is called by ProcessInterval to add nodes to the
// interval being constructed, and it is also called recursively as it walks
// the source graph.  A node is added to the current interval only if all of
// its predecessors are already in the graph.  This also takes care of keeping
// the successor set of an interval up to date.
//
// This method is templated because it may operate on two different source
// graphs: a basic block graph, or a preexisting interval graph.
void ProcessNode(Interval *Int, NodeTy *Node) {
  assert(Int && "Null interval == bad!");
  assert(Node && "Null Node == bad!");

  BasicBlock *NodeHeader = getNodeHeader(Node);

  if (Visited.count(NodeHeader)) {     // Node already been visited?
    if (Int->contains(NodeHeader)) {   // Already in this interval...
      return;
    } else {                           // In other interval, add as successor
      if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
        Int->Successors.push_back(NodeHeader);
    }
  } else {                             // Otherwise, not in interval yet
    for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
           E = IGT::child_end(Node); I != E; ++I) {
      if (!Int->contains(*I)) {        // If pred not in interval, we can't be
        if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
          Int->Successors.push_back(NodeHeader);
        return;                        // See you later
      }
    }

    // If we get here, then all of the predecessors of BB are in the interval
    // already.  In this case, we must add BB to the interval!
    addNodeToInterval(Int, Node);
    Visited.insert(NodeHeader);     // The node has now been visited!

    if (Int->isSuccessor(NodeHeader)) {
      // If we were in the successor list from before... remove from succ list
      llvm::erase_value(Int->Successors, NodeHeader);
    }

    // Now that we have discovered that Node is in the interval, perhaps some
    // of its successors are as well?
    for (typename GT::ChildIteratorType It = GT::child_begin(Node),
           End = GT::child_end(Node); It != End; ++It)
      ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
  }
}

这是最关键的算法部分，第一个ProcessInterval函数以 Node 作为 Header, 开始寻找以此为 Header 的 Interval(通过调用第二个 ProcessInterval)。然后把找到的 Interval 和对应的 Successors 迭代器入栈, 然后在operator ++()里面每次搜索 IntStack 里所有 Successors 作为 Header 的 Interval，其实这是一种Interval 层面的 BFS。 同时注意，如果已经 visited 改 Node, 就返回 false, 说明这次没有找到 Interval。

我们接下来看 Interval 里面的图算法,也就是第二个ProcessInterval函数里的逻辑。

如果 Visited[Node]:

  • 若 Interval 里已经有这个 Node 了，就结束这次寻找
  • 若没有，说明在别的 Interval 里，也就是说，是本 Interval 的 Successor 之一

若没有 Visited

  • 若逆向搜索发现 Pred(Node)不在 Interval 里，则说明我们没有搜完 Node 的 Preds， 也就是还不能 dominate Node， 先退出让 Preds 先被搜完 (BasicBlock 层面的 BFS, 其实还是会 see you later)
    • 若 Node 不是 Successor，先加进去，后面再删除。\((1)\)

然后把 Node 加进 Interval 里，若 Node 之前是 Successor 现在取出，对应的是情况\((1)\)

最后继续搜索子节点，直到所有对应的 Node 都被加进来，注意这里 Interval 的前一个 Interval 的 Successors 是未更新的， 这也就是为什么 IntervalPartition 类要调用updatePredecessors(I)。