你好 今天，我想再次谈谈静态分析。 再说一次C ++。 唯一的是，与PVS-Studio不同，我们不会在程序中查找任何错误（尽管它们不仅查找错误），而且查找的不是最佳编写的地方。 这些地方之一是为程序中的数据选择一个容器。 如果您对我感兴趣，那么欢迎猫！
问题
在CoreHard 2018秋季大会（即将召开的非常好的会议上）中，我谈到了C ++编译器目前无法很好地进行优化。 我的抱怨之一是编译器无法优化程序中容器的使用。 让我们看一些代码示例。
void foo() { std::vector<int> v(42); }
看起来在这种简单的情况下，编译器应该能够优化此功能并简单地抛出std :: vector类型的变量声明，因为从C ++ 14开始，编译器可以删除动态内存分配，但是编译器不允许。 原因是目前只有一个C ++编译器实现了用于删除动态分配的优化-Clang。 到目前为止，所有其他编译器都不知道如何执行此操作。 但是，即使Clang在少数情况下也可以做到这一点。
在这种情况下，我们可以用std :: array替换std :: vector，前提是所选向量的大小不要太大，因为我们可能没有足够的堆栈来进行这种替换。 这样的替换将消除为堆分配的相当昂贵的内存，而且好处是，当使用std :: array时，编译器已经可以从函数中完全抛出std :: array了！
如果我们在谈论性能优化，我们建议考虑以下示例：
void foo() { std::vector<int> v; for(int i = 0; i < 42; ++i) { v.insert(v.begin(), 42); } for(const auto val : v) { std::cout << val << ' '; } }
在这种情况下，我们看到在std :: vector的情况下使用非常无效的操作-在容器的开头插入。 所有C ++程序员都知道这样做非常不好，因为它会使所有元素每次都移动，从而导致大量的复制/移动成本。 在这种情况下，最好将其替换为std :: list，而不关心插入位置或std :: deque（尽管在这种情况下，您可以清楚地看到您并不需要使用insert。但这只是一个示例，并非如此）更多:)
我们来看另一个示例代码：
void foo() { std::list<int> v; for(int i = 0; i < 3; ++i) { v.push_front(i); } for(const auto val : v) { std::cout << val << ' '; } }
在这种情况下，我们可以注意到我们可以用std :: forward_list轻松替换std :: list（是的，我知道很少有人使用它）。 在这种情况下，我们绝对不会丢失任何东西，但可以节省内存。 自然，编译器现在不进行这种优化。
在以下示例中，可以完成类似的操作：
void foo() { std::deque<int> v; for(int i = 0; i < 3; ++i) { v.push_back(i); } for(int i = 0; i < 3; ++i) { std::cout << v.back() << ' '; v.pop_back(); } }
在这里，我们可以看到我们真正需要的不是std :: deque，而是std :: stack。 这不能称为优化，因为std :: stack是适配器，并且默认情况下，它在内部使用std :: deque（除非用户另行指定）。 在这里我们可以更多地讨论语义优化，即 简化代码以使其易于理解。 在我看来，这也很重要。 如果您问：“也许这样的替代品还会带来性能提升吗？”，我会回答“也许。 请在您的标准库版本中查看实施细节。”
好吧，我认为有足够的例子。 你们每个人也可以提出很多建议。
使用的手段
为了实现静态分析器，我使用了LLVM软件包的一部分Clang Static Analzyer（CSA）和Clang Tidy。 我选择了这些工具，因为我认为它们是静态分析开放工具中最有前途的。 另外，Clang提供了其他静态分析器无法吹嘘的最高质量的C ++解析器之一（除非它们当然使用libclang）。
CSA和Clang Tidy都是静态分析器，它们都是LLVM的一部分。 有什么区别？ 区别在于Clang Tidy旨在编写简单的检查，基本上包括在抽象语法树上找到某种模式，显示某种警告，并可能自动将其替换为另一种警告。 您可以
在此处了解有关Clang Tidy的更多信息。
CSA旨在编写更多的“严重”和资源密集型（从实现的角度以及从执行时间/所花费的内存的角度来看）的检查。 例如，那里有一个符号执行机制。
我决定在CSA中实施检查，因为它在我看来并不常见，而且将来它会越来越难。 由于该静态分析器与各种IDE进行了
许多集成，因此决定通过Clang Tidy运行。
我们将如何（尝试）解决问题
首先，值得引入一些相当严格的限制，这些限制主要与以下事实有关：到目前为止，这只是一个原型：
- 仅在职能层面进行分析； 此限制意味着功能之间以及翻译单元之间将不进行任何分析。 为了简化此分析的实施而对功能之间的分析施加了限制，并且将来可以通过对整个翻译单元（而不仅仅是对每个功能）运行静态分析来相对容易地解决。 CSA中的现有限制对翻译单元之间的分析施加了限制，该限制将很快得到解决（承诺已经涌入上游）；
- 仅支持有限数量的容器。 通过为新容器添加新规则，在将来相对容易解决此问题。
- 仅用于分析抽象语法树。 因为是原型设计，所以这是最简单的分析类型。 为了获得更准确的结果，当然，您可以尝试至少使用符号执行，但是这种方法有其缺点。 您可以在此处阅读有关方法的更多信息。
现在，原型实现了以下简单算法：
- 首先，在抽象语法树上，我们找到负责声明我们支持的容器类型变量的顶点。
- 然后，我们找到与这些容器相关的操作，对其进行分类，并将此信息保存在临时缓存中。
- 在功能结束时，我们将分析收集到的统计信息，并根据预定义的规则对容器的使用提出建议。
目前，容器操作的分类如下（将来会扩展）：
- 在容器顶部添加一个项目。
- 在容器中间添加一个项目。
- 在容器的末尾添加一个项目。
- 从容器的开头删除项目。
- 从容器中间取出物品。
- 从容器末端取出物品。
目前分类不完整，即使在此列表上也无法正常工作。 例如，即使在开始时执行插入操作，分析器也被归类为插入到中间，尽管实际上根本没有。
打击误报
在任何静态分析中，误报是主要的头痛。 如果它们太多，那么有用的消息就会在垃圾中丢失。 因此，在这种情况下，您必须非常保守地采取行动，并且仅在我们对诊断确实有信心并且可以肯定地说代码中某些地方确实存在错误的情况下发出警告。
如果我们谈论的是编译器优化，那还很难过–适当的优化无法根据C ++标准更改程序的行为（否则，这种优化器毫无用处）。 而且优化也不应引入悲观性：)因此，在这里您必须更加谨慎地进行决策。
在此分析器中，这种挣扎导致以下事实：如果分析器发现当前正在执行某些不受支持的操作，则将关闭对此容器的分析。
缺点和可能的解决方案
这种方法存在几个问题。
第一个问题是，对于分析器而言，目前代码的所有分支都是同等概率的。 更准确地说，他甚至不知道代码执行的不同分支。
这会转化为类似以下代码的分析问题：
void foo(int* ptr, std::vector<int>& v) { if(ptr == nullptr) { v.insert(v.begin(), 42); } else { v.push_back(84); } }
在我们的应用程序中，这些代码分支最有可能没有相等的执行概率，因为在现实世界中，指针通常表示正常的东西，而不是nullptr。 在同一个LLVM中，此分数具有静态试探法。 例如，它考虑了上述情况，比较了指针与nullptr的值，以及相互比较带有浮点数的两个变量的值的相等性，以及其他一些有趣的情况。 但这越来越像拐杖，从我的角度来看，解决此问题的真正方法是添加动态分析或工具。
第二个问题是缺乏对自定义容器的支持。 我们生活在C ++的世界中，他们喜欢骑在这里（包括我们的容器在内）（让我们离开本文讨论范围之内的这种并非总是不好的现象的原因的讨论）。 示例包括相同的LLVM，LibreOffice等。 在这方面，出现了一个问题-如何分析不是来自STL库的容器？ 毕竟，我想对尽可能多的容器进行分析。
有多种解决方法。
首先是用户以某种方式对容器进行注释（一种特殊的注释，C ++属性，等等）。 这种方法的问题在于，我们需要了解一般如何注释，定性分析需要哪些信息。 另一个问题可能是容器本身的代码修改，这并非总是可能的。
第二种方法为用户提供了一种编写自己的规则的机制。 目前，分析器中的规则已缝入分析器本身的源代码中，如果用户要添加自己的规则，则他将需要下载分析器的源代码，对其进行汇编，弄清楚如何编写检查，编写，重建等等。 您可以为用户提供一种在DSL上设置其支票的方法，其中用户只为他的容器编写支票，而分析器将参与整个例程。 我认为这种方法比前一种方法更有希望。
另外，不支持自动容器替换，因为此功能不在CSA中（但在Clang Tidy中）。 但是在困难的情况下，执行“自动更正”并不总是一件容易的事，并且分析仪更有可能在半手动模式下工作。
可能的应用
我看到了几种用于这种类型分析的应用程序：
- 就像静态分析仪一样。 一切都很简单-静态分析的另一项测试，您可以按照自己的意愿运行（在开发过程中，在开发过程中自动在IDE中自动操作，在CI等上），在那里可能会提示您可以在某个地方进行操作拿起一个更好的容器。
- 就像在编译器中进行优化一样。 在某些情况下，我们可以保证更换容器绝对不会对性能造成负面影响。 例如，当我们不需要双向连接并且我们不从列表中获取大小时，可以将std :: vector替换为在编译时已知的小尺寸std :: array或将std :: list替换为std：forward_list。 编译器可能在我们不知情的情况下，用更优的容器替换了容器，因为它已经处理了很多事情。
- 就像一个动态分析仪。 在我看来，这是此类分析最有前途的方向。 的确，例如，借助有关程序执行配置文件的知识，我们可以为我们获取诸如每个代码分支执行的概率之类的重要信息。 这对于更准确的评估是必要的。 通过这样的分析，您已经可以考虑与PGO集成的方向...
还值得注意的是，这种方法当然不仅适用于C ++程序。 我真的很想在编译器和其他编程语言中看到这种静态分析/优化。 例如，用于ABAP的SAP静态分析器已经知道如何在基本级别上进行静态最优性分析，这是一个好消息。 如果您知道其他编程语言的类似项目，请在注释中写些内容，我将在本文中添加内容！
在相似的方向上工作
对于C ++世界，我在任何地方都找不到这种分析器。 对于ABAP领域，我提到了上面的分析器，该分析器可以发现部分标准容器的低效操作，但据我所知，在那里执行了非常简单的静态分析。
Chameleon是更有趣的工作，它是Java的动态分析器，它非常巧妙地完成了工作。 他们对JVM进行了一些调整，并在操作过程中收集了有关容器使用情况的各种统计信息，并且根据当前的负载配置文件，他们选择了某些容器并在操作期间自动替换了它们。 不幸的是，消息来源是封闭的，没有机会获得它们（我尝试过）。
我还建议您查看
SETL上的各种作品（很多）。 在其中，作者还经常提出有关容器自动选择的问题。
参考文献
- 当前在github上的实现
- C ++俄罗斯2017：Yuri Efimochev，整洁：C ++抽象语法树内的旅程
- 变色龙：集合的自适应选择
- 铛静态分析仪指南
- 关于Telegram编译器开发的俄语聊天 。 如果您有兴趣，请进来，那里很有趣。 只是小心洪水-他们会立即惩罚他:)
除了结论以外，我还想强调一个事实，即到目前为止，它只是一个原型，并且在实施中有太多的“漏洞”。 在本文中，我只想与您分享这种分析及其推广的想法。 好吧，也许有人会对这个话题感兴趣，并且会有连接到该项目的愿望-我只会很高兴！ 此外，您始终可以在自己的地方收集该分析仪，以在测试示例中进行尝试。
如果您需要补充材料，遇到类似问题或仅获得一些对本主题有用的信息-请不要犹豫，在评论中分享此信息。
感谢您的关注！