C++ 中公共子表达式消除的局限性

Question

我在看一个演讲，“效率与算法，性能与数据结构，并且是对以下评论感到惊讶：

#include <string>
#include <unordered_map>
#include <memory>

struct Foo {
  int x;
};

Foo* getFoo(std::string key,
            std::unordered_map<std::string,
                               std::unique_ptr<Foo>> &cache) {
  if (cache[key])
    return cache[key].get();

  cache[key] = std::unique_ptr<Foo>(new Foo());
  return cache[key].get();
}

Foo* getFooBetter(std::string key,
                  std::unordered_map<std::string,
                                     std::unique_ptr<Foo>> &cache) {
  std::unique_ptr<Foo> &entry = cache[key];
  if (entry)
    return entry.get();

  entry = std::unique_ptr<Foo>(new Foo());
  return entry.get();
}

getFooBetter() 更好。我一直相信我可以依靠在编译器上执行这种转换我希望 x+y 多次出现的方式只被评估一次。毫不奇怪，生成的 LLVM IR 确实与主持人。即使使用 -O9，我们仍然有 3 次调用 cache[key] getFoo() 版本。

我已将长 LLVM IR of both with c++ symbols unmangled 移到不符合标准的位置，以免造成视觉上的冒犯。

Another Whosebug question 揭示了这里的部分答案是 operator[] 假定能够修改它希望的任何全局状态，并且因此我们不能省略电话。 A linked proposal关于介绍一个 [[pure]] 注释谈论它在 CSE 中的应用。

如果我们停留在 4 个电话，我就能在这里结束时感到满意。然而，如果我对 IR 的解读是正确的，那么看起来我们优化了 getFoo() 就像我们写的一样：

Foo* getFoo(std::string key,
            std::unordered_map<std::string,
                               std::unique_ptr<Foo>> &cache) {
  if (cache[key])
    return cache[key].get();

  std::unique_ptr<Foo> &entry = cache[key];
  entry = std::unique_ptr<Foo>(new Foo());
  return entry.get();
}

有人能解释一下 clang 对代码的看法吗？它能够合并最后两个 cache[key]，但不是全部他们？（我本地的 clang 是 3.4。）

Answer 1

unordered_map 查找中发生了很多事情。有散列计算，搜索一个 bin，如果它不存在则添加到 bin，如果 table 现在太大了，可能会增加它。这与比较代码中有两个 "x+y" 实例不同。你应该更惊讶它实际上发现两个调用可以合并。（我是。）

作为一般规则，我不会指望编译器发现可以共享两个函数调用，并且，当性能很重要时，我会自己在源代码中删除公共子表达式。在完全实现 constexpr 之前，我什至不希望它会发现 sin(x) 是相同的。

Answer 2

llvm 中的 CSE 实现对算术表达式进行运算。你可以在 llvm/lib/Transforms/Scalar/EarlyCSE.cpp

中查看 llvm Common Subexpression Elimination 源代码

我们在这里遇到的案例是过程间优化。

这个调用cache[key]原来是[](cache,key)函数。因此，根据 [] 函数的内联成本，内联等优化可能会起作用。 Chandler 提到了同样的问题，考虑到散列函数的计算成本很高，内联被阻止，最终不止一次计算散列函数！

如果发生内联，首先计算 -O3 处的 IR，cache[key] 并且给定 cache key 根本没有突变，这样的调用将被优化为相同的 SSA 值。

在cache[key].get()的情况下，我们通常会将IR写成cache[key] returns对象，并使用get()中的getelementpointer获取字段的值。启用优化后，此 IR 变成了我们之前计算的“缓存[key]”的 SSA 值，其中元素从唯一指针的结构访问。

回到 getFooBetter() 在最坏的情况下，如果编译器无法跨过程进行优化，cache[key] 出现的次数越多，计算量就越大，即使在 O3 处，这个调用也会按原样出现！

C++ 中公共子表达式消除的局限性

Limitations of Common Subexpression Elimination in C++

c++

clang

compiler-optimization