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

本文探讨如何结合动态与静态分析来优化C++代码性能，重点介绍使用CodeQL检测类型别名导致的性能问题，并通过实际案例展示如何实现10倍以上的性能提升。

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

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

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

有多种方法可以修复这个“问题”。在可能的情况下，用char8_t替换uint8_t/char类型将解决它。char8_t类型在C++20中引入，没有char的别名问题。如果无法使用C++20，并且切换到其他更宽的原始类型不合理，那么另一个选项是尝试将任何需要从内存加载的代码提升到循环之外。对于简单的代码，这可以很直接，例如将访问向量的size()属性提升到循环条件之前。然而，对于更大、更复杂的循环，这可能很快变得不可行，并且可能不得不接受由于类型别名导致的不必要内存加载的开销。

搜索别名写入

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

我们想要搜索的代码序列如下所示：

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

乍一看，这似乎是静态分析器匹配的一组相当容易的属性。我们不会担心跨函数边界的推理（尽管我们将处理内联函数），并且每个属性都可以表示为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]处的写入无法影响它，并且该值本可以存储在寄存器中并重用。事实上，通过别名类型的写入在这里导致两次额外的内存读取，因为在部分[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]处的写入，向量的大小将在循环的每次迭代中不必要地重新加载。

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

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

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

用于查找别名写入的CodeQL查询

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

 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。我们立即可以看到，表达像“从内存读取”这样的汇编级概念要求我们枚举我们认为可能产生此类汇编的C/C++级语法构造。这有可能引入误报和漏报。它还将导致我们的查询非常冗长，即使我们可以用自然语言简洁地表达我们想要匹配的属性。

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

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

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

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

用于查找涉及数组表达式、指针解引用和指针字段访问的代码模式的查询实现都非常相似，因此我将仅在此处介绍指针字段访问的查询（在Github上找到，辅助函数在这里）。指针字段访问包括诸如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然后立即覆盖它，但请记住，这是一种声明性查询语言，而不是命令性语言。我们陈述baseVar等于两件事，因此它们必须相同。 我们还需要断言在a1和a2处访问的字段相同。 最后，我们指定在a1和a2之间baseVar未被修改。上述情况指定在a1和a2之间没有左值是基变量的赋值表达式。在完整查询中，我们还处理了基变量可能被修改的其他几种方式。

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

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

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

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

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.getLocation().getFile().getBaseName(), l.getLocation().getStartLine(), l, w

通过isMemCharWriteExpr [1]以与我们早期查询相同的方式处理写入内存部分，并且我们添加了写入表达式在循环内部的要求[2]。loopConditionAccessesMemory是我们将用于查找循环条件的谓词，

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次