Chinaunix首页 | 论坛 | 博客
  • 博客访问: 960022
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类:

2009-04-13 18:32:36

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则完成实际的向量语句生成、修改循环退出条件等等向量化
的工作。这个函数之前已经由分析确定当前循环可以被向量化,所以该函数不会失败。
阅读(3898) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~