gcc向量化.doc

1向量化驱动，下面列出了向量化需要做的工作。 analyze_loop_CFG(loop) 检查loop中控制流的特性（基本块的个数，嵌套，入口出口等等），以便确定loop的控制流是否属于可以向量化的形式。 analyze_loop_index_and_bound(loop) 分析loop结束条件以便确定loop边界和索引变量的性质（边界和步长）。这种功能函数需要得到规约变量分析器的支持。 analyze_loop_stmts(loop-stmts) 扫描loop中的语句，检查是否有不能向量化的语句，如函数调用等。 analyze_access_pattern(loop-mem-refs) 分析loop中的内存引用，并按照它们的存取形式进行分类 analyze_alignment(loop-mem-refs) loop中内存引用的对齐分析，对于每一个内存引用来说，如果在编译时可以确定未对齐的数量，就将其记录下来。 analyze_loop_carried_dependences(loop) 建立循环依赖图（标量和数组引用），检查图中的强连通分量（引起循环依赖的语句集），用拓扑方法将图简化（每个强连通图都表示为一个节点）；只有那些没有自依赖的才能被向量化。如果还有其他的强连通分量，就需要做loop变换了。 estimate_vectorization_profitability(loop) 在这之前已经确定loop是可量化的，还需要确定它的向量化是否是有利可图的（也就是评估向量化的收益）。 vectorize_loop(loop) 用对应的向量化语句（将调用内置的函数）来替代标量语句，同时相应的改变循环边界。 2基本向量化 这一部分描述了一个基本向量化的方案，它提供了对上术工作的最小的支持。列出了loop基本向量化的一些约束条件。基本向量化认为下面的形式是可行量化的： for(i=0; iN; i++) {a[i] = b[i] + c[i]; } 1 最内层循环 单基本块循环，换言之，没有if-then-else结构等（实际上是指loop中含有两个基本块） 其他的约束（。。。。。。） 2 处理简单的规范loop（什么是规范的loop），并且有一个简单的终止条件 循环边界在编译时可确定 Loop边界=向量-size并且loop边界%向量-size = 0 3 简单操作（标量和向量有一一对应关系的操作） 不支持标量扩张，规约变量，归约操作等 不支持混合数据类型（所有的语句操作必须是对于同样的数据类型） 4 只支持数组引用的内存存取 只支持连续的存取形式（步长为单位长度） 5 所有的非对齐内存引用在编译时能确定 非对齐引用为0（都是对齐的） 6 处理没有任何强连通分量的（没有循环依赖的）loop 只允许loop-index的循环携带依赖 用最简单的循环检测 7 只有当loop_bound = MIN_LIMIT 时才向量化 8 应用scalar-to-vector mapping. 3向量化历史 4.1 2004.01.01 可向量化循环的描述： 1最内存循环只含有一个基本块（没有if-then-else） 2循环的迭代次数在循环执行前就可以确定。 3循环边界已知，可以被向量化因子（每条向量指令可以并行执行的数据宽度） 4循环索引变量从0到N，并且步长为1，循环条件是iN的形式。 5所有内存存取的都是一维数组。 6所有的数组存取都是连续的（跨度都是1），并且是对齐的。 7根据目标平台的向量化支持情况，支持的操作包括加减乘。 8所有的操作都必须针对相同长度的数据类型。 9不允许有规约（如sum += a[i]）和归纳(如 a[i] = i)。 10循环中不允许有常数和不变量（如 a[i] = 5） 即如下形式的循环： int a[256], b[256], c[256]; foo () { int i; for (i=0; i256; i++){ a[i] = b[i] + c[i]; } } 4.2 2004.06.04 新功能： 1循环边界（迭代次数）可以是未知的，3 2去掉了循环索引变量和循环条件形式的约束。4 3可向量化操作又添加了一些位操作，与或异或等。7 4常数和不变量得到了支持（a[i]= 5, a[i] = x）。10 int a[256], b[256], c[256]; foo (int n, int x) { int i; /* feature: support for unknown loop bound */ /* feature: support for loop invariants */ for (i=0; in; i++) b[i] = x;