LLVM学习笔记（16）补

V7.0 的实现如下。第一个版本的 InlinePatternFragments() 是所有外部调用的入口，即让一个 TreePattern 实例内联其中的片段。类型 TreePatternNodePtr 是 std::shared_ptr 。

864  void InlinePatternFragments() {

865  std::vector Copy = Trees;

866  Trees.clear();

867  for (unsigned i = 0, e = Copy.size(); i != e; ++i)

868  Copy[i]->InlinePatternFragments(Copy[i], * this , Trees);

869  }

容器 Trees 里保存的是由当前 PatFrags 派生定义里的 Fragments 域中（ list ）每个片段所创建的 TreePatternNode 实例。在上面 865 行 Trees 容器里的对象被移到了 Copy 临时容器中，然后对每个片段的 TreePatternNode 实例调用下面 TreePatternNode 的 InlinePatternFragments() 进行展开。

1858  void TreePatternNode::InlinePatternFragments (

1859  TreePatternNodePtr T, TreePattern &TP,

1860  std::vector &OutAlternatives) {

1861 

1862  if (TP.hasError())

1863  return ;

1864 

1865  if (isLeaf()) {

1866  OutAlternatives.push_back(T);  // nothing to do.

1867  return ;

1868  }

1869 

1870  Record *Op = getOperator();

1871 

1872  if (!Op->isSubClassOf("PatFrags")) {

1873  if (getNumChildren() == 0) {

1874  OutAlternatives.push_back(T);

1875  return ;

1876  }

1877 

1878      // Recursively inline children nodes.

1879  std::vector > ChildAlternatives;

1880  ChildAlternatives.resize(getNumChildren());

1881  for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {

1882  TreePatternNodePtr Child = getChildShared(i);

1883  Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]);

1884        // If there are no alternatives for any child, there are no

1885        // alternatives for this expression as whole.

1886  if (ChildAlternatives[i].empty())

1887  return ;

1888 

1889  for ( auto NewChild : ChildAlternatives[i])

1890  assert ((Child->getPredicateFns().empty() ||

1891  NewChild->getPredicateFns() == Child->getPredicateFns()) &&

1892  "Non-empty child predicate clobbered!");

1893  }

1894 

1895      // The end result is an all-pairs construction of the resultant pattern.

1896  std::vector Idxs;

1897  Idxs.resize(ChildAlternatives.size());

1898  bool NotDone;

1899  do {

1900  // Create the variant and add it to the output list.

1901  std::vector NewChildren;

1902  for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i)

1903  NewChildren.push_back(ChildAlternatives[i][Idxs[i]]);

1904  TreePatternNodePtr R = std::make_shared(

1905  getOperator(), std::move(NewChildren), getNumTypes());

1906 

1907  // Copy over properties.

1908  R->setName(getName());

1909  R->setPredicateFns(getPredicateFns());

1910  R->setTransformFn(getTransformFn());

1911  for (unsigned i = 0, e = getNumTypes(); i != e; ++i)

1912  R->setType(i, getExtType(i));

1913 

1914  // Register alternative.

1915  OutAlternatives.push_back(R);

1916 

1917  // Increment indices to the next permutation by incrementing the

1918        // indices from last index backward, e.g., generate the sequence

1919        // [0, 0], [0, 1], [1, 0], [1, 1].

1920  int IdxsIdx;

1921  for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {

1922  if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size())

1923  Idxs[IdxsIdx] = 0;

1924  else

1925  break ;

1926  }

1927  NotDone = (IdxsIdx >= 0);

1928  } while (NotDone);

1929 

1930  return ;

1931  }

1932 

1933  // Otherwise, we found a reference to a fragment.  First, look up its

1934    // TreePattern record.

1935  TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);

1936 

1937  // Verify that we are passing the right number of operands.

1938  if (Frag->getNumArgs() != Children.size()) {

1939  TP.error("'" + Op->getName() + "' fragment requires " +

1940  Twine(Frag->getNumArgs()) + " operands!");

1941  return ;

1942  }

1943 

1944    // Compute the map of formal to actual arguments.

1945  std::map ArgMap;

1946  for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {

1947  const TreePatternNodePtr &Child = getChildShared(i);

1948  ArgMap[Frag->getArgName(i)] = Child;

1949  }

1950 

1951  // Loop over all fragment alternatives.

1952  for ( auto Alternative : Frag->getTrees()) {

1953  TreePatternNodePtr FragTree = Alternative->clone();

1954 

1955  TreePredicateFn PredFn(Frag);

1956  if (!PredFn.isAlwaysTrue())

1957  FragTree->addPredicateFn(PredFn);

1958 

1959  // Resolve formal arguments to their actual value.

1960  if (Frag->getNumArgs())

1961  FragTree-> SubstituteFormalArguments (ArgMap);

1962 

1963  // Transfer types.  Note that the resolved alternative may have fewer

1964      // (but not more) results than the PatFrags node.

1965  FragTree->setName(getName());

1966  for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i)

1967   FragTree->UpdateNodeType(i, getExtType(i), TP);

1968 

1969      // Transfer in the old predicates.

1970  for ( const TreePredicateFn &Pred : getPredicateFns())

1971  FragTree->addPredicateFn(Pred);

1972 

1973      // The fragment we inlined could have recursive inlining that is needed.  See

1974      // if there are any pattern fragments in it and inline them as needed.

1975  FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives);

1976  }

1977  }

TreePatternNode 如果是 PagFrags 定义里的叶子节点，它的 Val 域是非空的， Operator 域是空的；如果是非叶子节点，则反之。因此，到达 1870 行的都是非叶子节点。 1872~1931 行处理非 PatFrags 的派生定义。我们在前面看到对这样的 TreePatternNode 节点，其 Children 容器里保存的是对应 dag 定义里的操作数的 TreePatternNode 实例。

在 1881 行循环，对这些操作数执行深度优先的递归处理。这里，除非处理出错， ChildAlternatives 容器是不可能空的，另外，由于操作数有可能展开为多个，因此这个容器是二维的。操作数展开后，如果原来有谓词，展开前后谓词必须相同。

1889~1928 行循环执行这样的操作：这是一个深度自递归过程。假设这个 dag 有两个 PatFrags 操作数，分别展开为 2 个及 3 个结果。那么该循环要生成这两个操作数展开结果的完全组合，并对每对组合生成 TreePatternNode 实例。所生成的组合依次是： ([0][ 0 ], [1][ 0 ]), ([0][ 0 ], [1][ 1 ]), ([0][ 0 ], [1][ 2 ]), ([0][ 1 ], [1][ 0 ]), ([0][ 1 ], [1][ 1 ]), ([0][ 1 ], [1][ 2 ]), ([0][ 2 ], [1][ 0 ]), ([0][ 2 ], [1][ 1 ]), ([0][ 2 ], [1][ 2 ]) 。（假若 PatFrags 操作数展开的结果仍然是 PatFrags ，这些 PatFrags 结果在 1883 行的递归调用里先得到处理，与上面类似的结果保存在 ChildAlternatives 容器里，再进入 1899 行循环）。每对括号里的操作数与原来的操作符将一起生成一个 TreePatternNode 实例，然后这些实例保存在 OutAlternatives 容器里返回。

1935 行以下是处理 PatFrags 的派生定义作为片段 dag 操作符的情形。在这一行上获取该 PatFrags 派生定义对应的 TreePattern 实例，而它所在 dag 的操作数个数必须与这个 TreePattern 实例里 Children 容器保存的 TreePatternNode 实例个数相同（它们就是从 dag 的操作数解析来的）。剩下代码执行实参替换。

由上面的处理看到，一个片段的展开可能有多个结果，在这些结果里操作数已经组合好了，因此在 1946 行循环先将实参的 TreePatternNode 实例与实参名通过临时容器 ArgMap 关联，在 1952 行对片段的每个 TreePatternNode 实例执行实参替换（通过 SubstituteFormalArguments() 方法，与上面 v3.6.1 的处理相同）。最后在 1975 行对替换后的片段调用 InlinePatternFragments() 进行最后一轮的（可能的）展开。