c++ - C++ 中公共(public)子表达式消除的局限性

Question

我在看一个演讲，"Efficiency with Algorithms, Performance withData Structures" ， 并且是对以下评论感到惊讶:

#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 StackOverflow 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

llvm 中的 CSE 实现对算术表达式进行操作。你可以在 llvm/lib/Transforms/Scalar/EarlyCSE.cpp 中查看 llvm Common Subexpression Elimination 源代码

我们在这里面临的案例是过程间优化。

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

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

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

回到 getFooBetter() 在最坏的情况下，如果编译器无法跨过程进行优化，更多的 cache[key] 将导致更多的计算和此调用即使在 O3 也会按原样出现!