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,我们也会cache[key]在getFoo()版本中留下3个电话.

我已经移动了两个长的LLVM IR,其中c ++符号没有被标记为脱节,以免在视觉上令人反感.

另一个StackOverflow问题揭示了这里的部分答案operator[] 是假设能够修改它所希望的任何全局状态,因此我们不能忽略调用. 关于引入注释的链接提议将 [[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],但不是全部？(我当地的铿锵声是3.4.)

Answer 1

llvm 中的 CSE 实现是在算术表达式上运行的。您可以在 llvm/lib/Transforms/Scalar/EarlyCSE.cpp 中查看 llvm 公共子表达式消除源代码

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

这个调用结果cache[key]是[](cache,key)函数。因此，内联等优化可能会根据 [] 函数内联的成本而发挥作用。钱德勒提到了同样的问题，考虑到哈希函数的计算成本很高，内联被阻止，最终会多次计算哈希函数！

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

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

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