sixgill CFG 格式

sixgill 插件的主要输出是与每个编译函数关联的松散标记为控制流图 (CFG) 的内容。这些存储在 src_body.xdb 文件中，该文件包含从函数名称（“mangled$unmangled”）到函数数据的映射。

该图实际上是一组有向无环数据流图，通过暗示控制流图中后向边的“循环”拼接在一起。

函数数据是一个“主体”数组，一个主体用于函数中的顶级代码，另一个主体用于每个循环。主体 *不是* 基本块，因为它们可以包含内部分支。（主体中的节点不一定支配后续节点。）主体是一个 DAG，因此没有后向边或交叉边。尽管如此，流程仅从入口点开始，仅在出口点结束，（1）循环主体的入口点隐式地跟随其出口点，以及（2）Call 节点会导致实际程序计数器转到另一个（可能为递归）主体。主体实际上描述的是数据流，而不是动态控制流。

函数主体

主体（无论是顶级主体还是循环主体）包含

• .BlockId

  • .Kind: 对于顶级函数为“Function”，对于其内部的（可能嵌套的）循环为“Loop”。

  • .Loop: 如果 .Kind == “Loop”，则为一个字符串标识符，用于区分循环，格式为“loop#n”，其中 n 是主体中循环的索引。嵌套循环会将其扩展为“loop#n#m”。

  • .Variable:

    • .Kind: “Func”

    • .Name[]: 函数 Name（见下文）

• .Version: 始终为零

• .Command: 用于编译此函数的命令（如果已记录）。此命令 *不会* 包含 -fplugin 参数。

• .Location[]: 函数定义的第一行和最后行的源位置的长度为 2 的数组。希望它在同一个文件中。请注意，此 Location 与 PPoint.Location（见下文）不同，后者将具有单个源位置。每个源位置为

  • .CacheString: 文件名

  • .Line: 行号

• .DefineVariable[]: 主体中定义的变量列表。第一个是函数本身。每个变量都有

  • .Type: 变量的类型。见下文的 Type。

  • .Variable:

    • .Kind: 下列之一

      • “Func” 用于函数本身

      • “This” 用于 C++ this 参数

      • “Arg” 用于参数

      • “Temp” 用于临时变量

    • .Name[]: 变量 Name（见下文）

• .Index[]: 主体中第一个和最后一个索引的 2 元组。

• .PPoint[]: 主体中每个点的文件名和行号

  • .Location: 单个源点（见上文）。

• .PEdge[]: 主体的核心部分。见下文的边。

• .LoopIsomorphic[]: 主体中 {"Index": point} 点的列表，这些点在循环主体中被克隆。见下文边 Kind Loop。

循环主体（BlockId.Kind == “Loop” 的主体）此外还将具有

• .BlockPPoint: 对父主体中表示此循环入口点的点的完整引用的数组。每个都有

  • .BlockId: 父主体的 BlockId

  • .Index: 父主体中点的索引

  • .Version: 值为零，用于增量分析，但在 GC 危害分析中未使用。

请注意，循环可能出现在多个父主体中。我相信这在常规结构化代码中不会使用，但在使用 goto 时可能需要正确地解开循环。

Name: 包含变量或函数名称的 2 元组。第一个元素是原始的内部名称，第二个元素是面向用户的名称。对于非函数，两个元素通常相同，但如果同一个函数的不同作用域中有多个同名变量，则 .Name[0] 可能带有 :<n> 后缀，或者对于静态变量，则带有 <file>: 前缀。对于函数，.Name[0] 是函数的全名（格式为“mangled$unmangled”)，.Name[1] 是函数的基本名称（未限定，没有类型或参数）

"Variable": {
  "Kind": "Func",
  "Name": [
    "_Z12refptr_test9v$Cell* refptr_test9()",
    "refptr_test9"
  ]
}

主体是“点”之间“边”的数组。所有行为都描述为发生在这些边上。body.Index[0] 给出主体中的第一个点。每条边都有一个源点和一个目标点。因此，例如，如果 body.Index[0] 为 1，则（除非主体为空）将至少有一条边 edge.Index = [1, 2]。代码 if (C) { x = 1; } else { x = 2; }; f(); 将有两条边共享一个共同的目标点

Assume(1,2, C*, true)
Assign(2,4, x := 1)
Assume(1,3, C*, false)
Assign(3,4, x := 2)
Call(4,5, f())

请注意，以上语法是 xdbfind src_body.xdb <functionName> 默认输出的一部分。它是 xdbfind -json src_body.xdb <functionName> 提供的完整 JSON 输出的简化版本。在本文档中，它将用于描述示例，因为 JSON 输出过于冗长。

每个主体都是一个有向无环图 (DAG)，存储为一组带有源点、目标点二元组的边。原始流图中的任何循环都将替换为 Loop 边（见下文）。

边

边存储在名为 PEdge 的数组中，具有以下属性

• .Index[]: 给出源点和目标点的 2 元组。

• .Kind: 7 种不同的 Kind 之一。其余属性将取决于此 Kind。

Sixgill 将控制流图分解为一小部分边 Kind

赋值

• .Exp[]: 赋值的 [lhs, rhs] 的 2 元组，每个都是表达式（见下文的 Expressions）。

• .Type: 表达式的整体类型，我相信是 lhs 的类型？（见下文的 Types）。

请注意，当函数调用的结果被赋值给变量时，Call 也用于赋值。

调用

• .Exp[0]: 表示被调用函数（“被调用者”）的表达式。被调用者可能是一个简单的函数，在这种情况下 exp.Kind == "Var"。或者它可能是计算出的函数指针或其他内容。该表达式计算出被调用的函数。

• .Exp[1]（可选）：将返回值分配到的位置。

• .PEdgeCallArguments[]: 表达式的数组，每个表达式对应一个传递的参数。这并不包括 this 参数。

• .PEdgeCallInstance: 用于调用方法的对象的表达式，它将作为 this 参数传递。

假设

Assume 节点目标可以依赖于给定的值假设，例如 Assume(1,2, __temp_1* == 7) 表示在点 2 处 __temp_1 将为 7。

条件分支将表示为从分支条件表达式出来的 Assume 边对。这些边生成一个数据流图，其中如果变量已通过 Assume 边（至少在到达 Assign 或 Call 边之前），则可以知道该变量的值。

• .Exp: 正在测试的表达式。

• .PEdgeAssumeNonZero: 如果存在，则将其设置为 true，表示我们处于 Exp 不等于 0 的边上。如果不存在，则 Exp 为 0。

示例：C++ 函数主体

SomeRAIIType raii;
if (flipcoin()) {
  return 1;
} else {
  return 2;
}

可能会生成类似以下内容

Call(3,4, __temp_1 := flipcoin())
Assume(4,5, __temp_1*, true)
Assume(4,6, __temp_1*, false)
Assign(5,7, return := 1)
Assign(6,7, return := 2)
Call(7,8, raii.~__dt_comp ())

循环

边对应于整个循环。“循环”的含义很微妙。它主要是将一般图形转换为一组无环 DAG 所需的，方法是查找后向边，并从后向边目标（循环入口点）和后向边源之间的子图创建“循环主体”。（具有共同目标的多个后向边将构成一个循环。）只有对某个后向边（由其后支配）必要的顶级主体节点才会被移除。共享节点将被克隆，并出现在顶级主体和循环主体中。克隆的节点被描述为“同构”。

• .BlockId : 循环主体的 BlockId。

• .Loop : 类似“loop#0”的 id，它将与相应循环主体的 .BlockId.Loop 属性相匹配。

示例：考虑以下 C++ 代码

float testfunc(int val) {
  int x = val;
  x++;
loophead:
  int y = x + 2;
  if (y == 8) goto loophead;
  y++;
  if (y == 10) return 2.4;
  if (y == 12) goto loophead;
  return 3.6;
}

这将生成循环主体

block: float32 testfunc(int32):loop#0
parent: float32 testfunc(int32):3
pentry: 1
pexit:  6
Assign(1,2, y := (x* + 2))
Assume(2,6, (y* == 8), true)  /* 6 is the exit point, so loops back to the entry point 1 */
Assume(2,3, (y* == 8), false)
Assign(3,4, y := (y* + 1))
Assume(4,5, (y* == 10), false)
Assume(5,6, (y* == 12), true) /* 6 is the exit point, so loops back to the entry point 1 */

以及顶级主体

block: float32 testfunc(int32)
pentry: 1
pexit:  11
isomorphic: [4,5,6,7,9]
Assign(1,2, x := val*)
Assign(2,3, x := (x* + 1))
Loop(3,4, loop#0)
Assign(4,5, y := (x* + 2))       /* edge is also in the loop */
Assume(5,6, (y* == 8), false)    /* edge is also in the loop */
Assign(6,7, y := (y* + 1))       /* edge is also in the loop */
Assume(7,8, (y* == 10), true)
Assume(7,9, (y* == 10), false)   /* edge is also in the loop */
Assign(8,11, return := 2.4)
Assume(9,10, (y* == 12), false)
Assign(10,11, return := 3.6)

同构点对应于 C++ 代码

y = x + 2;
if (y == 8) /* when y != 8 */
y++;
if (y == 10) /* when y != 10 */

这是为了到达后循环边 Assume(9,10, (y* == 12), false) 而执行的代码。（如果到达顶级主体中的点 9 并且 y *等于* 12，则不会选择 Assume(9,10,...) 边。顶级主体中的点 9 对应于循环主体中的点 5，因此将选择边 Assume(5,6, (y* == 12), true)。）当“控制流”位于同构点时，可以认为它同时位于该点的所有“实例化”处。实际上，这些是有向无环数据流图，其中循环的出口点从外部已知流入入口点，并且顶级主体缺少任何会使其成为循环的 Assume 或其他后向边。

对于 while 循环，同构点将评估条件表达式。

另一个示例：C++ 代码

void testfunc() {
  static Cell cell;
  RefPtr<float> v10;
  v10.assign_with_AddRef(&somefloat);
  while (flipcoin()) {
    v10.forget();
  }
}

生成

block: void testfunc():loop#0
parent: void testfunc():3
pentry: 1
pexit:  4
Call(1,2, __temp_1 := flipcoin())
Assume(2,3, __temp_1*, true)
Call(3,4, v10.forget())

block: void testfunc()
pentry: 1
pexit:  7
isomorphic: [3,4]
Call(1,2, v10.assign_with_AddRef(somefloat))
Loop(2,3, loop#0)
Call(3,4, __temp_1 := flipcoin())
Assume(4,5, __temp_1*, false)
Call(5,6, v10.~__dt_comp ())

第一块是循环体，第二块是主体。主体的第 3 点和第 4 点等价于循环体的第 1 点和第 2 点。注意循环体的“parent”字段，它给出了循环入口点在主体中的等价点（3）。

汇编

一段不透明的汇编代码。

注释

我不确定我是否见过这些？它们可能是针对旧的注释机制的。

跳过

这些似乎是内部的“epsilon”边，用于简化图构建和循环分割。在发出最终 CFG 之前，它们会被移除。

表达式

表达式是 CFG 的主体。

• .Width（可选）：以位为单位的宽度。我不确定何时使用它。对于类型来说，拥有宽度要常见得多。

• .Unsigned（可选）：布尔值，表示此表达式是否无符号。

• .Kind：以下值之一

程序左值

• “Empty”：在不需要任何内容的有限上下文中使用。

• “Var”：引用变量的表达式

  • .Type

• “Drf”：解引用（例如，*foo 或 foo->… 或某些隐式内容）

  • .Exp[0]：正在解引用的目标

  • .Type

• “Fld”

  • .Exp[0]：包含字段的目标对象

  • .Field

    • .Name[]：[限定名称，非限定名称] 的 2 元组

      • 可以是未命名的，在这种情况下，名称将是“field”。这用于基类。

    • .FieldCSU：字段所属的 CSU 的类型

    • .Type：字段的类型

    • .FieldInstanceFunction：“此字段是否是虚拟实例函数而不是包含 CSU 的数据字段”。存在或不存在才是重要的。我看到的所有示例都是纯虚函数（virtual void foo() = 0）。

    • .Annotation[]：特定字段上的任何注释

• “Rfld”：？某种“反向”字段访问

  • 与 Fld 相同的子节点

• “Index”：数组元素访问

  • .Exp[0]：目标数组

  • .Index：正在访问的索引（一个 Exp）

  • .Type：元素的类型

• “String”：字符串常量

  • .Type：字符串的类型

  • .Count：字符串中元素（字符）的数量

  • .String：字符串中的实际数据

• “Clobber”：“内存模型生成的额外左值”（？）

  • 被调用者

  • 覆盖

  • 可选的值种类

  • 点

  • 可选位置

程序右值

• “Int”，“Float”：常数值

  • .String：值的字符串形式（这是存储值的唯一方式）

• “Unop”，“Binop”：运算符

  • .OpCode：各种操作码

  • .Exp[0] 和 .Exp[1]（后者仅限于 Binop）：参数

  • 步长类型（可选）

表达式修饰符

• “Exit”，“Initial”：？

  • .Exp[0]：目标表达式

  • 值种类（可选）

• “Val”：？

  • 左值

  • 值种类（可选）

  • 索引（主体点）

  • 布尔值，表示它是否为相对的（？）

• “Frame”：（未使用）

不可变属性

这些似乎是为我们未使用的内置分析设计的合成属性。

• “NullTest”：？

  • .Exp[0]：正在测试的目标

• “Bound”：？似乎是边界检查的索引访问

  • 边界种类

  • 步长类型

  • .Exp[0]（可选）：边界适用的目标

• “Directive”：？

  • 指令种类

可变属性

这些似乎是为我们未使用的内置分析设计的合成属性。

• “Terminate”

  • 步长类型

  • 终止测试（Exp）

  • 终止整数（Exp）

  • .Exp[0]（可选）：目标

• “GCSafe”：（未使用）

  • .Exp[0]（可选）：目标

类型

• .Kind：正在描述的类型的种类，以下之一

可能的类型种类

• “Void”：C/C++ 中的 void 类型

• “Int”

  • .Width：以位为单位的宽度

  • .Sign（可选）：类型是否带符号

  • .Variant（可选）：？

• “Float”

  • .Width：以位为单位的宽度

• “Pointer”：指针或引用类型

  • .Width：以位为单位的宽度

  • .Reference：0 表示指针，1 表示普通引用，2 表示右值引用

  • .Type：目标的类型

• “Array”

  • .Type：元素的类型

  • .Count：元素的数量，以普通常数整数给出

• “CSU”：类、结构或联合体

  • .Name：限定名称，作为普通字符串

• “Function”

  • .TypeFunctionCSU（可选）：如果存在，则为包含函数的 CSU 的类型

  • .FunctionVarArgs（？）(可选)：如果存在，则函数为可变参数（例如 f(…))

  • .TypeFunctionArgument：参数类型的数组。如果至少有一个参数，则存在。

    • .Type：参数的类型

    • .Annotation（可选）：此参数的任何显式注释（attribute((foo)))

  • .Variable：表示函数的变量

  • .Annotation（可选）：此函数的任何显式注释

• “Error”：sixgill 在处理此类型时出现错误。可能是某些未实现的内容。