使用CodeQL在C++中寻找10倍以上性能提升：结合动态与静态分析进行性能优化

本文探讨如何结合动态与静态分析工具，特别是使用CodeQL来识别C++代码中的类型别名问题，这些问题会导致编译器生成不必要的内存读取，从而显著降低性能。通过实际案例展示了如何修改代码以消除这些问题，并实现高达12倍的性能提升。

使用CodeQL在C++中寻找10倍以上性能提升：结合动态与静态分析进行性能优化

在上一篇文章中，我提倡构建结合静态和动态分析的系统来进行性能优化。通过这样做，我们可以构建比单独使用任何一种分析方法更有用的工具。事实上，对于许多静态分析来说，是否有用很可能取决于它是否与性能分析器结合使用。例如，连续性能分析可以收集生产环境中最热门的代码路径信息，这可以用来对静态分析的输出进行排序。开发人员随后可以将精力集中在最重要的发现上。这最大限度地减少了由于静态分析的误报或不重要的真阳性而浪费的时间。相反，静态分析可以用来为连续性能分析的输出提供进一步的上下文，并使其结果更具可操作性，例如建议为什么某个特定函数可能是热门的，或者建议潜在的优化。

在上一篇文章中，我还概述了一个简单但非常有效的分析组合，其中连续性能分析确定的Top N最昂贵的函数被输入到一个服务中，该服务根据已知更快替换的列表检查库和函数名称，允许开发人员在零代码更改的情况下优化他们的应用程序。例如，将jemalloc替换为libc malloc，将zlib-ng替换为zlib，将orjson替换为Python的stdlib JSON等。

在这篇文章中，我们将更深入地探讨一个实际查看应用程序代码的静态分析。当我开始思考性能优化的分析组合时，我没有找到太多现成的静态分析工具可以直接使用。因此，我决定构建自己的工具。我们将尝试回答这个问题：我们能否使用静态分析来找到导致编译器发出次优机器代码的C/C++代码模式？

我将首先描述一个特定的代码模式，该模式可能导致编译器发出不必要的内存读取，并无法自动向量化循环。当这些模式存在时，它们可能导致函数比原本可能的速度慢10-20倍或更多。我将展示如何构建CodeQL查询来找到这些模式，以及如何修改代码以允许编译器自动向量化。然后，我将讨论将查询应用于几个代码库的结果，列出一些出现的问题，并详细说明一些潜在的未来工作和开放问题。

CodeQL

CodeQL允许您以声明性面向对象语言编写查询，并将这些查询应用于已转换为数据库中关系表示的代码库。换句话说，它提供了一种相对易于使用的查询语言，用于在代码中找到有趣的模式。通常，它在安全领域用于漏洞狩猎。从漏洞猎人的角度来看，CodeQL为静态分析工具提供了相对独特和强大的功能。现有的静态分析工具（如Coverity、clang静态分析器等）编码了对常见漏洞模式的检查，但由于这些工具本身就是许多软件开发人员工具箱的一部分，以及简单的溢出模式越来越不可能通过现代QA，因此这些分析器对漏洞猎人来说并不是特别有帮助。由于这个原因和其他原因，静态分析在寻找可利用软件缺陷的人群中并没有很好的声誉。通过允许方便地编码任意模式并在数据库中搜索它们，CodeQL实现了“变体分析”，即在同一个代码库或新代码库中搜索给定错误的变体。这被证明是寻找安全漏洞的一种富有成果的方式。到目前为止，CodeQL在检测性能问题领域还没有任何我已知的用途，但其灵活性使其成为任何可以编码为抽象语法树上的属性的优秀候选技术。

C/C++中类型别名的不便之处

在《用eBPF优化eBPF优化器》中，我讨论了在程序合成引擎中寻找性能改进。我做的优化之一是修改代码，以允许编译器自动向量化一系列非常热门的循环，这些循环看起来如下：

在底层，std::vector<bool>具有一些属性，意味着循环无法自动向量化。有关详细信息，请参阅我刚刚提到的帖子，但简而言之：我们需要将std::vector<bool>替换为不是bool的向量。我最初选择的是uint8_t，但令我惊讶的是，我没有得到一个很好的展开和向量化的循环，而是得到了这个：

编译器生成的代码在循环的每次迭代中从[r12]和[rbx+0xa8]加载源和目标指针，因此无法自动向量化。我最终在Travis Downs的这篇帖子的帮助下追踪到了问题。问题是类型别名。在C/C++中，char类型（及其同类，如uint8_t）可以别名任何其他类型。在通过此类类型写入内存时，编译器必须假设它可能修改了任何其他基于堆的内存位置，即使该位置具有完全不同的类型（例如上述示例中包含在源和目标向量中的数据指针）。因此，在上述示例中，编译器必须假设[r12]和[rbx+0xa8]可能已被对[rdx+rax]的写入修改，因此无法安全地自动向量化循环，因为它需要在每次写入后重新加载这些值。

在许多情况下，必须从内存重新加载值并不是世界末日，但在循环的上下文中，这个问题可能导致编译器生成的代码比原本可能的情况 drastically worse。在Travis的博客文章中，他展示了一个特别病态的示例，其中问题导致代码比原本可能的速度慢20倍。

有多种方法可以修复这个“问题”。在可能的情况下，将uint8_t/char类型替换为char8_t将解决它。char8_t类型在C++20中引入，没有char的别名问题。如果无法使用C++20，并且切换到其他更宽的原始类型不合理，那么另一个选项是尝试将任何需要从内存加载的代码提升到循环之外。对于简单的代码，这可能是直接的，例如将访问向量的size()属性的代码提升到循环条件之前。然而，对于更大、更复杂的循环，这可能 quickly become infeasible，并且可能 stuck with accepting the overhead of unnecessary memory loads due to type aliasing。

搜索别名写入

我们的目标是构建一个查询，该查询将找到代码中的模式，其中由于通过别名类型的写入，编译器正在生成我们知道是不必要的内存加载。让我们首先 high level 描述我们在寻找什么。

我们想要搜索的代码序列看起来像：

  1. 通过表达式X从内存加载，其中X表示内存位置。例如，X可能的形式为*a、a[i]、*(a+i)等。
  2. 随后通过别名类型（如char）进行写入。
  3. 随后通过X从内存加载，使得表达式X的组件自步骤(1)以来没有被修改。例如，如果表达式X是*(arr+i)，那么我们需要arr和i都没有被修改。如果它们被修改了，那么编译器将需要发出另一个从内存的加载， regardless of the write through the aliasing type。

乍一看，这似乎是静态分析器匹配的一组相当容易的属性。我们不会担心跨函数边界的推理（尽管我们将处理内联函数），并且每个属性都可以表示为AST上的语法谓词。

在以下示例中，标记为[1]、[2]和[3]的代码对应于上述列表中的项目1、2和3。

上述模式将匹配一个直线序列，如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// glib-2.0/glib/gstring.h
static inline GString*
g_string_append_c_inline (GString *gstring,
                         gchar    c)
{
 if (gstring->len + 1 < gstring->allocated_len) // 1
   {
     gstring->str[gstring->len++] = c; // 2
     gstring->str[gstring->len] = 0; // 3
   }
 else
   g_string_insert_c (gstring, -1, c);
 return gstring;
}

这里[1]标记了通过读取gstring->len的第一次内存加载，[2]标记了通过将c写入gstring->str的别名类型的写入，[3]标记了通过再次读取gstring->len的第二次读取。由于[2]，编译器被迫在[3]处生成gstring->len的第二次加载，尽管我们可以看到[2]处的写入 cannot impact it，并且该值本可以存储在寄存器中并重用。事实上，通过别名类型的写入在这里导致两次额外的内存读取，因为在部分[3]处，编译器不仅必须重新加载gstring->len，还必须重新加载gstring->str。您可以在Compiler Explorer上查看为此生成的汇编。

该模式还将匹配稍微更复杂的循环，例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// tesseract/src/classify/adaptmatch.cpp
     for (unsigned id = 0; id < templates->NumClasses; ++id) { // 1,3
       int font_set_id = templates->Class[id]->font_set_id;
       const FontSet &fs = fontset_table_.at(font_set_id);
       for (auto f : fs) {
         const Shape &shape = shape_table_->GetShape(f);
         for (int c = 0; c < shape.size(); ++c) {
           if (char_norm_array[shape[c].unichar_id] < pruner_array[id]) {
             pruner_array[id] = char_norm_array[shape[c].unichar_id]; // 2
           }
         }
       }
     }

（这里[1]和[3]标记了templates->NumClasses的第一次和第二次加载，而[2]标记了对类型为uint8_t*的pruner_array的写入。由于别名写入，此示例中实际上必须从内存重新加载其他几个值，而不仅仅是templates->NumClasses。）

我们描述的模式不仅匹配上述最外层循环，还匹配第7行的最内层循环，因为shape是一个向量，并且对size()函数的调用将被内联。

1
2
3
4
5

// tesseract/src/classify/adaptmatch.cpp
         for (int c = 0; c < shape.size(); ++c) { // 1,3
           if (char_norm_array[shape[c].unichar_id] < pruner_array[id]) {
             pruner_array[id] = char_norm_array[shape[c].unichar_id]; // 2
           }

由于[2]处的写入，循环的每次迭代都将不必要地重新加载向量的大小。

为了使这些示例 full circle，让我们实际进行所需的更改以消除别名问题。跳回到glib示例，原始版本可以在Compiler Explorer上找到 here，优化版本（其中我们将char类型替换为C++20的char8_t类型）可以找到 here。下面，左边是原始版本，右边是使用char8_t的版本。

在原始版本中，第79到81行对应于gstring->str[gstring->len] = 0。rdi寄存器指向GString结构，字符串指针在偏移量0处，长度在偏移量8处。我们可以看到，由于第78行的写入，编译器必须考虑其可能与GString对象的内部别名，因此发出了从内存加载两者的代码。在使用char8_t的优化版本中，我们可以看到编译器不必担心别名写入，并为这行代码生成了单个指令：第78行。该指令重用了先前加载到rcx和rax中的字符串指针和字符串长度。

总之，我们有一个可以用简单英语描述的模式来找到代码模式，并且我们有证据表明，如果我们能找到这样的代码模式，那么我们可以进行微不足道的更改，从而可能使编译器发出更高效的代码。现在让我们继续构建CodeQL查询来自动搜索此模式。

CodeQL查询以找到别名写入

我们在概念上搜索的内容非常简单：两次内存加载，中间有一次通过别名类型的写入。在CodeQL中最容易表达的部分是写入，它看起来如下（我已将我们将构建的所有CodeQL查询放在此存储库中，此示例可以找到 here）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

predicate isMemCharWriteExpr(Expr e) {
   exists(AssignExpr a, Expr lval |
     a = e.(AssignExpr) and // A
     lval = a.getLValue() and
     lval.getType().stripType() instanceof CharType and // B
     (
       lval instanceof PointerDereferenceExpr or // C
       lval instanceof ArrayExpr or // C
       lval instanceof OverloadedArrayExpr // C
     )
   )
}

如果传递给它的表达式匹配“一个赋值表达式（A），其中左值具有字符类型（B）并且左值是指针解引用、数组表达式或重载数组表达式（C）”，则此谓词返回true。我们 immediately see here that expressing an assembly level concept like “a read from memory” requires us to enumerate the C/C++-level syntactic constructs that we think may produce such assembly. This has the potential to introduce both false positives and false negatives. It will also result in our queries being quite verbose, even though in natural language we can concisely express the properties we want to match on.

递增和递减运算符也可能导致对内存的写入（例如v[x]++），因此我们的谓词还必须考虑这些。它们可以以类似于赋值表达式的方式处理，因此为简洁起见，我未在此处呈现查询的那部分，但您可以在Github上找到完整谓词 here。

接下来，我们需要一种方法来匹配我们认为将产生内存加载的C/C++代码，这些加载具有我们概述为序列中项目1和项目3的属性。为此，我们需要构建一个查询，该查询匹配同一函数中的两个表达式，这些表达式将导致内存加载，理论上，如果不是因为中间的通过别名类型的写入，编译器可以将第一次加载的结果缓存在寄存器中并在第二次加载中重用。在C中有几种不同的语法结构可能导致内存加载。我们可能有：

  • 数组表达式，例如x = array[offset]
  • 指针解引用，例如x = *ptr
  • 指针字段访问，例如x = ptr->val

除此之外，我们还可能内联导致内存读取的函数，例如向量的size()函数。

用于查找涉及数组表达式、指针解引用和指针字段访问的代码模式的查询实现都非常相似，因此我将仅在此处 walk through the one for pointer field accesses here（在Github上找到 here，辅助函数 here）。指针字段访问包括诸如base->field之类的内容。在以下代码中，a1表示我们的第一次内存访问，w表示通过字符类型对内存的写入，a2表示我们的第二次内存访问。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from Expr w,  PointerFieldAccess a1, PointerFieldAccess a2, Variable baseVar
where 
   isMemCharWriteExpr(w) and // [1]
   // Sequence of execution is a1 -> w -> a2
   a1 = w.getAPredecessor+() and // [2] 
   w = a2.getAPredecessor+() and // [2]
   baseVar = a1.getQualifier().(VariableAccess).getTarget() and // [3]
   // Assert that a1 and a2 use the same base pointer
   baseVar = a2.getQualifier().(VariableAccess).getTarget() and // [3]
   // Assert a1 and a2 access the same field in the struct
   a1.getTarget() = a2.getTarget() and // [4]
   // Eliminate cases where the variable holding the base pointer is modified
   not exists(AssignExpr redef | // [5]
       redef = a1.getASuccessor+()
       and redef = a2.getAPredecessor+()
       and redef.(AssignExpr).getLValue().(VariableAccess).getTarget() = baseVar
   )
   // Further cases here to eliminate things like increments, redeclarations etc
   ... 
select a1.getLocation().getFile().getBaseName(), a1.getLocation().getStartLine(), a1, w, a2, baseVar

我们首先将写入表达式w传递给我们的谓词，以断言它是将导致内存解引用的字符类型的写入。 然后我们断言三个表达式的顺序，即a1在w之前，w在a2之前。 我们需要从base->ptr获取基变量，以便稍后对其断言。我们从a1中提取它并将其分配给baseVar，然后还断言a2使用相同的基变量。虽然这可能看起来像是我们将某些东西分配给baseVar然后立即覆盖它，但请记住，这是一种声明性查询语言，而不是命令性语言。我们 stating that baseVar equals two things, therefore they must be the same. 我们还需要断言在a1和a2处访问的字段是相同的。 最后，我们指定在a1和a2之间baseVar没有被修改。上述情况指定在a1和a2之间没有左值是基变量的赋值表达式。在完整查询中，我们还处理了基变量可能被修改的其他几种方式。

就是这样！此查询以及类似的指针解引用和数组表达式查询足以找到我们正在寻找的模式。它将在直线代码序列和循环中找到它们。如所呈现的，这些查询在单个函数的本地范围内操作。它们不会找到内存访问来自调用内联函数的情况，例如vector.size()。在下一节中，我将展示如何处理这种情况，因为有必要检测循环条件中的内联函数调用，这是我们正在搜索的内存访问类型的富有成果的来源。

在循环条件中查找内联内存访问

满足我们要求的内存加载的一个常见来源是循环条件中包含内联函数调用的加载，例如检查向量大小的内容，如for (i = 0; i < vector.size(); i++)。我们可以修改我们现有的搜索两次内存访问和中间别名写入的查询，因为它们是循环条件包含内存访问和该循环体内别名写入的情况的泛化。然而，我从CodeQL中学到的一个教训是，通常更容易为您心目中的确切内容构建查询，并在必要时 later generalise。过早的泛化可能导致过于复杂的查询，难以调试，并且容易产生误报和漏报。从具体示例开始，然后在必要时泛化，通常被证明是更好的策略。

我们希望找到的具体示例如下：

1
2
3
4
5

void vector8_inc(std::vector<uint8_t> &v) {
   for (size_t i = 0; i < v.size(); i++) {
       v[i]++;
   }
}

因此，我们想要一个循环，其中：

  1. 条件有一个调用内联函数的调用，该函数导致内存访问，并且
  2. 在循环体内有对内存的写入。

表达此内容的CodeQL查询开始如下：

1
2
3
4
5
6
7
8

from Loop l, Expr w
where 
// The loop condition accesses memory in some way
loopConditionAccessesMemory(l)
// And the loop contains a character-write expression
and isMemCharWriteExpr(w) // [1]
and w.getEnclosingStmt().getParentStmt*() = l.getStmt() // [2]
select l
comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次