GCC：辅助数据结构

辅助数据结构[编辑源代码]

GCC 具有许多有助于代码开发的附加数据结构，例如向量和堆。

vec.h 中定义的宏实现了一组模板化向量类型和 关联的接口。这些模板是用 宏，因为我们不在C++领域。接口功能有 typesafe 并使用静态内联函数，有时由 行外泛型函数。向量设计为 与GTY机械互操作。

由于结构对象的行为不同，标量 对象和指针，有三种风格，每种风格对应一种 这些变体。指针和结构对象变体 传递指向周围对象的指针 -- 在前一种情况下，指针 存储到向量中，在后一种情况下，指针是 取消引用，并将对象复制到向量中。标量 object variant 适用于类 int 对象，而 vector 元素按值返回。

同时存在“index”和“iterate”访问器。迭代器 返回布尔迭代条件并更新迭代 通过引用传递的变量。因为迭代器将是 内联，地址可以优化。

向量是使用尾随数组惯用语实现的，因此 如果不更改矢量的地址，它们就无法调整大小 对象本身。这意味着您不能有 向量类型 -- 始终使用指向向量的指针。唯一的例外 是结构的最后一个字段，可以是向量类型。 您必须使用embedded_size和embedded_init调用 创建这样的对象，它们可能无法调整大小（所以 不要使用“安全”分配变体）。尾随数组 使用惯用语（而不是指向数据数组的指针），因为， 如果我们允许 NULL 也表示一个空向量，则空向量 在包含它们的结构中占用最小的空间。

每个增加活动元素数量的操作都是 提供“快速”和“安全”型号。前者假定 有足够的分配空间使操作成功 （如果没有，它就会死）。后者将重新分配 向量，如果需要。重新分配导致 向量大小。如果您知道您将添加 N 个元素，它会 在添加 元素与“快速”操作。这将确保有 最少你要求的元素，它会成倍增长 如果备用插槽太少，则增加。如果您想预订 特定数量的插槽，但不希望呈指数级增长 （例如，您知道这是最后一次分配），使用 预订的负数。您还可以创建一个向量 从一开始就具有特定的尺寸。

您应该更喜欢 push 和 pop 操作，因为它们会附加 和 从向量的末尾移除。如果您需要删除多个 项目 在一次中，使用截断操作。插入和删除 操作允许您在中间更改元素 向量。有两个删除操作，一个保留 元素排序为“ordered_remove”，而元素排序不 'unordered_remove'。后一个函数复制结束元素 添加到已删除的插槽中，而不是调用 memmove 操作。这 “lower_bound”功能将确定将项目放置在 使用插入的数组，它将保持排序顺序。

定义矢量类型时，首先要定义非内存托管版本 已创建。然后，您可以定义一个或两个垃圾回收 和堆分配的版本。指定分配机制 当类型被定义时，因此是类型的一部分。如果 您需要 GC'd 和 HEAP 分配的版本，您仍然必须有一个通用的非内存托管基本向量的定义。

如果您需要直接操作向量，则“地址” accessor 将返回向量开头的地址。也 “space”谓词将告诉您是否有备用容量 在向量中。您通常不需要使用这两个函数。

向量类型使用 DEF_VEC_{O，P，I}（TYPEDEF） 宏定义，以 获取非内存分配版本，然后获取 DEF_VEC_ALLOC_{O，P，I}（TYPEDEF，ALLOC） 宏来管理内存 向量。向量类型的变量是使用 VEC（TYPEDEF，ALLOC） 宏。ALLOC 参数指定 分配策略，可以是垃圾的“GC”或“堆” 分别收集和堆分配。它可以是“没有”得到的 必须显式分配的向量（例如，作为 另一个结构的尾随数组）。字符 O、P 和 I 指示 TYPEDEF 是指针 （P）、对象 （O） 还是整数 （一）类型。小心选择正确的一个，因为你会得到一个 如果您使用错误的 API，则会造成尴尬且效率低下的 API。有一个 检查，这会导致 P 和 I 的编译时警告 版本，但没有检查 O 版本，因为这不是 由于 GTY 的工作方式，您必须注释 您希望插入或引用的任何结构 GTY（（）） 标记。即使您从未声明 GC，也需要这样做 分配的变体。

它们使用的一个例子是，

 DEF_VEC_P(tree);   // non-managed tree vector.
 DEF_VEC_ALLOC_P(tree,gc);    // gc'd vector of tree pointers.  This must
                              // appear at file scope.
 
 struct my_struct {
   VEC(tree,gc) *v;      // A (pointer to) a vector of tree pointers.
 };
 
 struct my_struct *s;
 
 if (VEC_length(tree,s->v)) { we have some contents }
 VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end
 for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
   { do something with elt }

其他表示[编辑源代码]

图 2 显示了 GCC 4.1 的其他表示形式。

由于语言的差异，每种语言生成的 AST 的格式略有不同。生成 AST 后的下一步是统一步骤，其中 AST 树转换为称为泛型的统一形式。在此之后，编译器的中间端部分将进行控制。首先，将树转换为另一种称为 GIMPLE 的表示形式。在这种形式中，每个表达式包含的操作数不超过三个，所有控制流构造都表示为条件语句和 goto 运算符的组合，函数调用的参数只能是变量等。 图 2 说明了通用形式的树和 GIMPLE 形式的树之间的区别。GIMPLE 是用于优化源代码的便捷表示。

在 GIMPLE 之后，源代码将转换为静态单一赋值 （SSA） 表示形式。这种形式的中心思想是，每个变量只分配给一次，但可以在表达式的右侧多次使用。每次重新分配 GIMPLE 形式的树的相同变量时，编译器都会创建该变量的新版本并将新值存储到其中。当在条件表达式的两个分支中分配相同的变量时，需要将变量的两个可能值合并为一个变量。此操作在 SSA 形式中表示为 PHI 函数。

SSA 表单也用于优化。GCC 对 SSA 树执行了 20 多种不同的优化。SSA 优化通过后，树将转换回 GIMPLE 表单。