86 5.5.2 符号符号表表 OMPi 对符号表的高层管理是使用 symtab 结构体，其中 symtabl-table 是一个数组，记录了 STSIZE 个符号表项。Symbol.h 文件部分代码如下，首先是符号表的大小： 1. #define STSIZE 1031 /* Prime */ 符号表大小 然后是关于符号的名字空间问题。 可以看出符号分成几种名字空间， namespace 有 IDNAME标识符、TYPENAME 类型名、SUNAME 结构和联合体名、ENUMNAME 枚举名等 6 种。 2. typedef enum IDNAME = 1, TYPENAME, SUNAME, ENUMNAME, LABELNAME, FUNCNAME 3. namespace; 名字空间 再接着是符号表项指针和符号表项，符号表项是符号表的元素，它对符号 symble 进行了封装，不同的名字空间的符号借助于成员 space 来标示。所有的符号都在符号表里。一个符号使用符号项来记录，下面是符号项 stentry_的定义。 4. typedef struct stentry_ *stentry; 5. struct stentry_ symbol key; /* The symbol */ 指向符号 6. void *vval; /* General, to put anything */ 7. int ival; /* For int values (common case) */ 8. astspec spec; /* The specifier */ 9. astdecl decl; /* The bare declarator */ 10. astdecl idecl; /* initdeclarator (includes decl) */ 11. namespace space; /* 1 table for all spaces */ 12. int isarray; /* Non-scalar */ 13. int isthrpriv; /* 1 if it is a threadprivate var */ 14. int scopelevel; /* The scope it was declared in */ 15. stentry bucketnext; /* for the bucket */ 16. stentry stacknext; /* for the scope stack */ 17. ; 符号表项里面的 spec、decl 和 idecl 分别指向某个变量符号的类型、声明和带初始化声名的 AST 节点，用于后面代码变换时克隆变量相关的代码。因为 decl 只指向声明，而声明这种非语句节点是没有父结点指针的， 所以无法访问到初始化语句节点。 大多数情况下只需要 decl即可，如果带有初始化，那么需要使用 idecl。Vval 和 ival 设计本意是可以存放一些随机目的的数据， 实际上 OMPi 只在分析 OpenMP 数据子句的时候来保存类型 （例如 private、 firstprivate等，参见 x_clauses.c），而 vval 用于保存归约操作的类型。scopelevel 用于记录本符号所处的作用域层次，bucketnext 用于形成具有相同 hash 值得符号的 FILO 链表，stacknext 则是根据所遇到符号的次序形成的 FILO 链表（堆栈）。 下面是符号表的定义，需要记录当前的变量作用域的层次。 18. typedef struct symtab_ stentry tableSTSIZE; STSIZE 个符号表项 19. stentry top; /* Most recent in scope */ 20. int scopelevel; /* Current scope level */ 21. *symtab; 87 所有遇到的符号都在这这里有记录， 所有的 symbol 将按照地址指针的 hash 散列值插入到table 中，图 5.17 中每一个垂直链表对应相同的 hash 值，它们在 OMPi 中称作一个“桶”（bucket），符号项 stentry 的 bucketnext 字段就是用来形成这个链表用的指针。注意这里的stentry 并不关心符号的字符串，后者是在 symbol 结构中保存的。 图图 5.17 symtab-table 的数据结构示意图的数据结构示意图 5.5.3 符号表操作符号表操作 符号表的常见操作分成两种， 一种是关于符号名字字符串的操作， 另一类是关于符号的操作。 名字字串名字字串操作操作 这部分操作对应于 allsymbols 数组，有符号的插入、查找等。OMPi 使用 Symbol()来根据字符串查找符号所在的位置，如果找不到则为该字符串创建一个符号插入 allsymbols 中，再返回它所在的位置。Symbol_exists()则是判断一个字符串是否在符号表中。Symbols_allfree()则将allsymbols 的所有元素及其占用的空间清空，这个函数只在不再需要符号表时才调用。另外还有根据字符串来计算 hash 值得 hash()函数。 符号表操作符号表操作 符号表的操作常见的有插入 symtab_put()、释放 freestentry()和删除 symtab_remove()等操作。符号表操作中比较特殊的就是需要插入全局符号的时候，symtab_insert_global()就是用于此目的的，此时不能按普通方式插入到 hash 值对应的“桶”的上面，而是需要遍历这个桶并插入到 scopelevel=0 的符号前。 共有 STSIZE 个 stentry 项 符号指针 Hash 散列 key bucketnext symbol 88 5.5.4 作用域作用域管理管理 每当语法扫描时遇到将产生新的作用域， 不同作作用域上的同名变量/符号是互不相关的相互独立的变量/符号。以 parser.y 的复合语句为例看看语法分析中的作用域处理： 1. /* ISO/IEC 9899:1999 6.8.2 */ 2. compound_statement: 3. 4. 5. $ = Compound(NULL); 6. 7. | $ = sc_original_line()-1; scope_start(stab); 8. block_item_list 9. 10. $ = Compound($3); 11. scope_end(stab); 12. $-l = $2; /* Remember 1st line */ 13. 14. ; 此处复合语句 compound_statement 可以有两种产生式， 第一种是里面没有语法构造的空语句，第二种是里面有 block_item_list 的复合语句。对于第二种情况，当遇到第一个“”时需要用 scope_start()往符号表里面插入名字空间为 IDNAME 的“scopper”符号，表示新作用域的开始，并且将 symtab- scopelevel 增 1 表示进入更深层的作用域。每个符号都会记录自己所在的作用域。可以对作用域进行命名，最外层是全局变量作用域 scope 0，然后是 scope 1，逐层编号等等。在任何时刻，第 i 层作用域上可见的变量在第 i+1 层代码中是可见的（除非在第 i 层声明了同名变量），反之第 i+1 层定义的变量对第 0 层到第 i 层的代码是不可见的。 如果在 symtab 里面出现同名符号，那么它们将有相同的 hash 值从而保存在相同的“桶”中，再根据“桶”的 FILO 的堆栈特性，查找是总是返回最里层作用域的符号，这个特性正好符合 C 语言作用域的特点。 语法分析中，每当退出一个作用域，则关闭次作用域同时删除该作用域内的符号。当语法扫描退出一个第 i 层的作用域时（遇到“”），该作用域的所有符号都要清除，这不需要对symtal 进行扫描选出 scopelevel=i 的所有符号，而是顺着符号堆栈（由 stacknext 链表构成）逐个删除，因为最上层的就是最里层的作用域，直到遇到上次进入该作用域时插入的符号scopper为止。删除当前作用域内的符号可以由 scope_end()来完成。 5.6 小结小结 本章首先解释了OpenMP/C编译使用AST作为中间表示的原因AST保留了语法层次结构便于进行源代码变换。 然后结合 OMPi 编译器分析如何设计 AST 节点， 详细分析了语句节点、表达式节点、类型说明节点、声明节点和 OpenMP 节点的具体数据结构。最后介绍语法制导89 翻译技术， 结合 OMPi 代码分析如何在语法分析中插入语义动作从而通过创建各种 AST 节点并构建出 AST。 关于符号表的处理也在本章介绍， 不仅分析了符号表的数据结构， 还分析如何随着语法分析进入不同作用域而动态的管理各种符号。 90 6 第 6 章 并行域管理并行域管理 在以 AST 为基础进行源代码变换之前，需要先了解 OpenMP 制导指令的语义以及与 C 语言之间的语义差距， 然后才是如何使用源代码级的翻译变换来消除这些差距。 我们将在三个方面进行分析：并行域管理（第 6 章）、任务分担与线程同步（第 7 章）、变量数据环境控制（第 8 章）。 首先来考察并行域管理上的语义差距。OpenMP 应用程序的执行模式是 fork-Join。在每次进入并行域后将由 fork 操作产生出多个线程来执行计算任务；当退出并行域的时候执行 join操作，除了主线程外所有线程都被撤销。如果出现嵌套的并行域，那么这些 fork-join 执行过程中将出现多层的线程树结构。 由于并行域内往往需要执行任务分担， 所以并行域的管理需要能记录这些层次关系、并行域内的协作关系、辅助变量作用域的判断等等。由于 C 语言本身并没有并发执行的概念，即使操作系统提供的类似 pthreads 库可以产生并发线程，也不能直接支持 OpenMP，因此这些差距必须通过源代码翻译变换和运行库函数进行消除。 本章将讨论 OpenMP 编译器将如何在标准 C 语言的基础之上，借助于运行库的支持来完成并行域代码的封装、线程层次、编号、协作等管理功能，并给出各自的代码翻译变换的框架形式。 6.1 并行域并行域及其及其嵌套嵌套 在第 2 章中已经描述过并行域的概念。 每当遇到 parallel 制导指令， 将产生出多个 OpenMP线程并发执行直到 para