GCC中的自动向量化
在前面，我们已经分析过了GCC的Tree-SSA优化框架。这篇文章分析这个框架下的一个
优化——自动向量化。
打开passes.c文件后，在init_optimization_passes函数中，可以看到和向量化有关
的几个遍：all_lowering_passes中的pass_lower_vector（定义在tree-vect-generic.c
中），all_passes->pass_all_optimizations->pass_tree_loop->pass_vectorize（定义在
tree-ssa-loop.c中）遍及其子遍pass_lower_vector_ssa（定义在tree-vect-generic.c中
）和pass_dce_loop（定义在tree-ssa-dce.c中）。感觉上，pass_vectorize应该是主要的
优化遍，而其它几遍是辅助遍，所以，下面从pass_vectorize开始看起。
文件tree-ssa-loop.c中定义的是一些在Tree-SSA中间表示上对循环进行的优化的相关
工作。我只关心自动向量化这一遍。
{code}
struct tree_opt_pass pass_vectorize =
{
"vect", /* 遍名字 */
gate_tree_vectorize, /* 是否执行该遍的谓词 */
tree_vectorize, /* 该遍执行的函数 */
NULL, /* 用于遍的组织 */
NULL, /* 用于遍的组织 */
0, /* 遍号 */
TV_TREE_VECTORIZATION, /* 时间统计变量号 */
PROP_cfg | PROP_ssa, /* 该遍执行前需要cfg存在，并且程序处于
ssa表示中 */
0, /* 该遍不提供任何新属性 */
0, /* 该遍保持所有属性 */
TODO_verify_loops, /* 开始时需要做的事情 */
TODO_dump_func | TODO_update_ssa, /* 结束时需要做的事情 */
0 /* 导出相关的字母 */
};
/* gate函数非常简单，只要flag_tree_vectorize设置，并且当前的循环
不为空，就做自动向量化 */
static bool
gate_tree_vectorize (void)
{
return flag_tree_vectorize && current_loops;
}
/* 向量化的主函数直接调用vectorize_loops(定义在文件tree-vectorizer.c中)函数，然
后返回0. */
static unsigned int
tree_vectorize (void)
{
vectorize_loops (current_loops);
return 0;
}
{/code}
好了，我们已经看到自动向量化遍的入口了，之后就是对自动向量化的详细分析。这里的分析基于GCC4.2.2，因为最近做的事情是基于这个版本的。
在分析vectorize_loops函数之前，我们先看看几个相关的数据结构。
在GCC的Tree-SSA优化框架中，循环信息主要是由两个结构体表示的：struct loop和
struct loops. 前者保存一个自然循环的信息，而后者则用于组织一个函数内的所有自然
循环的信息。
{code}
/* 保存一个自然循环信息的结构体 */
struct loop
{
/* 在loops的数组中的下标 */
int num;
/* 循环头基本块 */
basic_block header;
/* Basic block of loop latch. 这个是什么？ */
basic_block latch;
/* 关于循环展开和剥离的信息，主要有两个成员，一个是展开的决定，一个是展开的次
数 */
struct lpt_decision lpt_decision;
/* 循环中的指令数 */
unsigned ninsns;
/* 每次迭代执行的平均指令数 */
unsigned av_ninsns;
/* 基本块数 */
unsigned num_nodes;
/* 循环嵌套深度 */
int depth;
/* Superloops of the loop. 这是什么？ */
struct loop **pred;
/* 在循环构成的树中的高度，它包含的循环的层数 */
int level;
/* 该循环的外层循环 */
struct loop *outer;
/* 第一个包含在该循环中的循环 */
struct loop *inner;
/* 与该循环同深度的下一个兄弟循环 */
struct loop *next;
/* 是该循环拷贝的循环 */
struct loop *copy;
/* 辅助信息，不同的遍可以设置不同的东西 */
void *aux;
/* 运行时可能执行的迭代次数,是一个INTEGER_CST或者一个包括符号名字的表达式。
一般不直接访问这个域，使用
number_of_iterations_in_loop */
tree nb_iterations;
/* 一个INTEGER_CST表示迭代次数的估计. NULL_TREE表示没有估计 */
tree estimated_nb_iterations;
/* 循环迭代的上界 */
struct nb_iter_bound *bounds;
/* 非空表示该循环只有一个出口，出口边存储在这里 (指向EXIT_BLOCK_PTR的边不算*/
edge single_exit;
/* “真”表示该循环没有loop carried数据依赖，所有的迭代可以以任意顺序执行
“假”表示可能存在 loop carried数据依赖 */
bool parallel_p;
};
{/code}
{code}
/* 组织一个函数中所有自然循环的结构体 */
struct loops
{
/* 循环的数目 */
unsigned num;
/* 循环的状态 */
int state;
/* 该数组存储了指向循环的指针，数组元素可能为NULL。这是因为循环已经被删除，但
是该结构还没有被更新。*/
struct loop **parray;
/* 指向循环层次树根的指针 */
struct loop *tree_root;
/* 从CFG得到的信息 */
struct cfg
{
/* 深度优先搜索的基本块序 */
int *dfs_order;
/* The reverse completion ordering of the basic blocks found in a
depth first search. 这是什么？ */
int *rc_order;
} cfg;
/* 多个应该归并的循环共享的循环头 */
sbitmap shared_headers;
};
{/code}
loop_vec_info类型是自动向量化附加在循环上面的主要信息。自动向量化的多个步骤
之间使用这个结构体传递信息。
{code}
/* 自动向量化相关的信息 */
typedef struct _loop_vec_info {
/* 该信息关联的循环 */
struct loop *loop;
/* 循环的基本块 */
basic_block *bbs;
/* 循环退出条件 */
tree exit_cond;
/* 循环的迭代数 */
tree num_iters;
/* 该循环是否可以被向量化 */
bool vectorizable;
/* 向量化因子/循环展开因子 */
int vectorization_factor;
/* 可能的非对齐的数据引用，根据这个进行循环剥离 */
struct data_reference *unaligned_dr;
/* 为数据对齐而进行的循环剥离:
peeling_for_alignment = X 意味着:
If X=0: 不做循环剥离；
If X>0: 剥离头X个迭代.
If X=-1: 生成运行时的测试来决定循环剥离的数目，使用unaligned_dr中的信息
*/
int peeling_for_alignment;
/* 检查指针或数组是否对齐的掩码 */
int ptr_mask;
/* 循环中所有的数据引用 */
VEC (data_reference_p, heap) *datarefs;
/* 循环中所有的数据依赖 */
VEC (ddr_p, heap) *ddrs;
/* 这里面的语句包含的数据引用是在运行时进行对齐检查（Loop Versioning）的候选者
*/
VEC(tree,heap) *may_misalign_stmts;
/* 源代码中的循环的位置 */
LOC loop_line_number;
} *loop_vec_info;
{/code}
好的，现在我们就可以读读循环自动向量化的控制框架了。
{code}
/* 这个函数是循环自动向量化的主入口，也是自动向量化的控制框架 */
void
vectorize_loops (struct loops *loops)
{
unsigned int i;
unsigned int num_vectorized_loops = 0;
/* 该函数设置dump信息相关的变量，包括verbose级别 */
vect_set_dump_settings ();
/* 分配位图来记录需要被重命名的虚变量, 这个位图是全局变量 */
vect_vnames_to_rename = BITMAP_ALLOC (NULL);
/* ----------- 向量化的主框架 ----------- */
/* 如果在该过程中新生成了一些循环，那么这些新循环的下标比已有循环的都大。记录
当前的循环数，使得我们只在当前已有的循环上面做变换，而不去考虑在变换中新生成的
循环, 该变量也是全局的。 */
vect_loops_num = loops->num;
for (i = 1; i < vect_loops_num; i++) /* 为什么从1开始？ */
{
loop_vec_info loop_vinfo;
struct loop *loop = loops->parray[i];
if (!loop) /* 跳过parray中空的指针 */
continue;
/* 全局变量，记录当前循环的源代码位置 */
vect_loop_location = find_loop_location (loop);
/* 分析当前循环，将分析结果记录在loop_vinfo指向的结构中，并使得该循环
的辅助信息也指向该结构,以备后用 */
loop_vinfo = vect_analyze_loop (loop);
loop->aux = loop_vinfo;
/* 如果分析返回的
* loop_vinfo为空，或者loop_vinfo中的是否可向量化的标志为假，则
* 该循环不能向量化，继续考察下一个循环 */
if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
continue;
/* 向量化当前循环 */
vect_transform_loop (loop_vinfo, loops);
num_vectorized_loops++;
}
vect_loop_location = UNKNOWN_LOC;
/* 打印必要的导出信息 */
if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS))
fprintf (vect_dump, "vectorized %u loops in function.\n",
num_vectorized_loops);
/* ---------- 析构自动向量化的数据结构 ----------- */
BITMAP_FREE (vect_vnames_to_rename);
for (i = 1; i < vect_loops_num; i++)
{
struct loop *loop = loops->parray[i];
loop_vec_info loop_vinfo;
if (!loop)
continue;
loop_vinfo = loop->aux;
destroy_loop_vec_info (loop_vinfo);
loop->aux = NULL;
}
}
{/code}
由上面的代码可以看到，自动向量化会按照current_loops中的数组的顺序，依次分析
、向量化每个循环。最重要的函数就是vect_analyze_loop和vect_transform_loop。前者对
一个循环做各种分析，以确定该循环能否进行向量化以及向量化的方式，并将所有的信息记
录在一个loop_vec_info指向的结构体中，而后者则根据这里面的信息做实际的变换，以向
量化目标循环。
下面，我们继续来看vect_anaylyze_loop这个函数，它定义在文件
tree-vect-analyze.c中。事实上，该函数也是一个框架函数，它组织了各种不同的分析。
它本身就是输出一些信息，并组织这些具体的分析函数。
1. vect_anaylyze_loop_form
检查LOOP在CFG方面的特点，包括嵌套层次，出口，入口情况等。有以下限制：
a. 最内层循环
b. 基本块数为2，分别是循环头和latch
c. 循环有pre-header
d. 循环有单一的入口和出口
e. 循环的退出条件必须足够简单，并且该循环的迭代数可以被分析(countable loop).
2. vect_anaylyze_data_ref
找到循环中所有的数据引用（对应于vdefs/vuses）并分析它们在循环中的演化。当前
仅仅处理简单的，对齐可以强制保证的数组引用和对齐的指针引用。
3. vect_analyze_scalar_cycles
将loop carried标量数据依赖环分类，其中由于virtual phi引起的单独在其他地方分
析。类别包括：
a. reduction, 目前不支持
loop1:
for (i=0; i sum += a[i];
b. induction, 目前不支持
loop2:
for (i=0; i a[i] = i;
c. invariant
d. unknow
下面的循环是可以向量化的：
loop3:
for (i=0; i a[i] = b[i];
因为由i引起的定义-使用环被认为是“不相关的”，i不需要被向量化，见
mark_stmts_to_be_vectorized.
4. vect_pattern_recog
寻找计算模式，对与每一个找到的支持的模式，插入一个新的可以被向量化的语句。
同时，也在struct_stmt_info中记录一些信息。其过程如下：
假设开始时我们有如下语句:
stmt in_pattern_p related_stmt vec_stmt
S1: a_i = .... - - -
S2: a_2 = ..use(a_i).. - - -
S3: a_1 = ..use(a_2).. - - -
S4: a_0 = ..use(a_1).. - - -
S5: ... = ..use(a_0).. - - -
并且，{S1,S2,S3,S4}被识别为一个模式，那么，建立一个新语句S6用于替代该模式，
将S6插入到模式的最后一条语句S4之前，如下填写相关域：
in_pattern_p related_stmt vec_stmt
S1: a_i = .... - - -
S2: a_2 = ..use(a_i).. - - -
S3: a_1 = ..use(a_2).. - - -
> S6: a_new = .... - S4 -
S4: a_0 = ..use(a_1).. true S6 -
S5: ... = ..use(a_0).. - - -
在vect_mask_stmts_to_be_vectorized中，S6会被标记为相关而S4不会，因为所有使用
S4结果的地方，都被S6的结果替换。{S1,S2,S3}仍然会保持不相关，除非会被其它向量
语句使用。
如果向量化成功，vect_transform_stmt会跳过{S1,S2,S3}(如果它们还是不相关的)，
向量化S6，并且在S6和S4中记录向量化的新的VS6语句。这样做是为了当我们需要向量
化使用S4的结果的语句时，可以知道从什么地方找。S4被跳过，S5照常向量化。
in_pattern_p related_stmt vec_stmt
S1: a_i = .... - - -
S2: a_2 = ..use(a_i).. - - -
S3: a_1 = ..use(a_2).. - - -
> VS6: va_new = .... - - -
S6: a_new = .... - S4 VS6
S4: a_0 = ..use(a_1).. true S6 VS6
> VS5: ... = ..vuse(va_new).. - - -
S5: ... = ..use(a_0).. - - -
之后的DCE遍无用的语句{S1，S2,S3,S4,S5,S6}：
VS6: va_new = ....
VS5: ... = ..vuse(va_new)..
如果向量化没有成功，那么DCE遍会删除S6（它的结果没人使用），得到原来的序列。
5. vect_mask_stmts_to_be_vectorized
数据流分析，确定哪些语句不需要被向量化。并不是一个循环中所有的语句都需要向量
化，例如
for i...
for j...
1. T0 = i + j
2. T1 = a[T0]
3. j = j + 1
中语句1和3就不需要向量化，循环控制和地址计算是不需要向量化的。
6. vect_analyze_data_refs_alignment
分析循环中数据引用的对齐.
7. vect_determine_vectorization_factor
当前支持的循环中需要向量化的数据类型必须是相同的，根据这个类型来确定VF。
8. vect_analyze_data_ref_dependences
分析循环中数据引用之间的依赖。目前支持的必须是语句之间没有任何数据依赖的。
9. vect_analyze_data_ref_accesses
分析循环中数据引用的访问模式，目前只支持连续访问。目前仅支持数组和指针访问。
10. vect_enhance_data_refs_alignment
该分析确定是否使用loop versioning或者循环剥离来达到循环中数据引用的对齐。
当前限制无论是loop versioning还是循环剥离，仅仅在原循环中向量化，新生成的循
环不进行向量化。这一分析需要一个代价模型。
11. vect_analyze_operations
分析循环中语句的操作是否是可以被向量化的操作。
如果上面的任何一个分析失败，则销毁已经分配的loop_vec_info结构，并返回NULL，
否则，设置loop_vec_info中的vectorizable为1，返回该结构。
函数vect_transform_loop则完成实际的向量语句生成、修改循环退出条件等等向量化
的工作。这个函数之前已经由分析确定当前循环可以被向量化，所以该函数不会失败。
阅读(4340) | 评论(0) | 转发(1) |
