Microsoft PowerPoint - compiler

Size: px

Start display at page:

Download "Microsoft PowerPoint - compiler"

徒燕
4 years ago
Views:

1 主要内容编译技术回顾程序设计语言理论张昱编译器的形式和阶段运行时数据的组织抽象机模型 ,yuzhang@ustc.edu.cn 中国科学技术大学计算机科学与技术学院张昱 : 程序设计语言理论编译技术回顾 2 编译器是什么 1. 编译器的形式和阶段源程序编译器 Compiler 目标程序编译器的形式编译器的主要阶段目标语言一种编程语言 CISCs( 复杂指令集 ) RISCs( 精简指令集 ) 面向多核 / 众核 GPUs FPGAs 量子计算机等张昱 : 程序设计语言理论编译技术回顾 4 编译器的阶段编译器的阶段 source program Front end 前端 Back end 后端 target program source program Front end 前端 Program input Lexical 词法分析器 Token Stream 记号流语法分析器 Tree 语法树 Semantic 语义分析器 Annotated Tree 带注解的语法树 Interm. Gen. 中间代码生成器 Symbol Table 符号表 Interm. Rep. 中间表示 Optimizer 代码优化器 Interm. Rep. 中间表示 Gen. 代码生成器 Lexical 词法分析器 Token Stream 记号流语法分析器 Tree 语法树 Semantic / Interm. Gen. 语义分析器 / 中间代码生成器 Symbol Table 符号表 Tree-walk routines 树遍历程序 Abstract Tree or other Interm. Rep. 抽象语法树或其他中间表示 Program output 张昱 : 程序设计语言理论编译技术回顾张昱 : 程序设计语言理论编译技术回顾 6 1

2 解释器 Java 编译器源程序.java 源程序解释器 Interpreter 翻译器 Translator (javac) 直接在上执行源程序中间表示 Intermediate Representation.class Java 虚拟机 Virtual Machine (java) 张昱 : 程序设计语言理论编译技术回顾张昱 : 程序设计语言理论编译技术回顾 8 编译器的其他形式交叉编译器 (Cross compiler) 在一个平台上生成另一个平台上的代码 PC arm-linux-gcc ARM 增量编译器 (Incremental compiler) 以增量地编译源程序, 只编译修改的部分, 如 Freeline 即时编译器 (Just-in-time compiler) 在运行时对 IR 中每个被调用的方法进行编译, 得到目标机器的本地代码, 如 Java VM 中的即时编译器预先编译器 (Ahead-of-time compiler ) 在程序执行之前将 IR 翻译成本地码, 如 ART 中的 AOT 张昱 : 程序设计语言理论编译技术回顾 9 Java 虚拟机类加载器 Class loader Java 字节码.class 即时编译器 JIT Compiler 字节码解释器 Bytecode Interpreter 机器代码 Machine code 垃圾收集器 Garbage collector 张昱 : 程序设计语言理论编译技术回顾 10 C 编译器 Java 虚拟机 C 源程序预处理器 Preprocessor (cpp).i 连接器 Linker (ld) 目标文件.o 库代码 Library routines 机器代码 Machine code C 编译器 Compiler (cc) 汇编.s 汇编器 Assembler (as) 张昱 : 程序设计语言理论编译技术回顾 11 张昱 : 程序设计语言理论编译技术回顾 12 2

Java 虚拟机 : 改善内存管理对象生命期分析 Free 指令插桩支持空间复用支持对象显示回收

运行时数据的组织运行时的数据组织地址空间活动记录 : 语言特征对其的影响张昱 :

0xFFFF880000000000-0xFFFFcFFFFFFFFFF 高地址

张昱 : 程序设计语言理论编译技术回顾 16 内嵌块的活动记录 (activation

3 Java 虚拟机 : 改善内存管理对象生命期分析 Free 指令插桩支持空间复用支持对象显示回收 Free 指令的支持 2. 运行时数据的组织运行时的数据组织地址空间活动记录 : 语言特征对其的影响张昱 : 程序设计语言理论编译技术回顾 13 简化的机器模型进程地址空间 :64 位 Linux Memory Static Data Heap Stack 低地址 0x 位 Linux 系统 : 使用低 48 位虚拟地址, 48 位至 63 位必须与 4 位一致 (26TB) 用户空间 : 低 128TB 0-0xFFFFFFFFFFF 内核空间 :64TB 0xFFFF xFFFFcFFFFFFFFFF 高地址 0x0000FFFFFFF0000 TASK_SIZE 张昱 : 程序设计语言理论编译技术回顾 1 张昱 : 程序设计语言理论编译技术回顾 16 内嵌块的活动记录 (activation record) 函数的活动记录控制链指向外围块在栈中的活动记录活动记录入栈设置新的控制链, 使之指向旧的 env ptr 将 env ptr 指向新的活动记录活动记录出栈用当前活动记录的控制链来重置 env ptr 返回地址函数返回时要执行的代码的位置返回值存储返回结果 ( 或其地址 ) 参数从调用者处获取的数据参数传递方式 : 传值传引用参数返回值返回地址控制链访问链保存的机器状态局部数据临时数据 Env. pointer 张昱 : 程序设计语言理论编译技术回顾 1 张昱 : 程序设计语言理论编译技术回顾 18 3

4 函数的活动记录控制链指向调用者的活动记录访问链指向在程序正文中包含其的最近外围块的活动记录支持过程定义嵌套时的非局部名字访问二者的区别控制链依赖于程序的动态行为访问链依赖于程序正文的参数返回值返回地址控制链访问链保存的机器状态局部数据临时数据 Env. pointer 高阶函数语言特征 : 函数是 first class values 函数可以作为参数被传递函数可以作为返回值返回需要维护函数所处的环境 ( 上下文 ) 静态作用域?( 上下文按程序正文中的静态包含关系 ) 动态作用域?( 上下文按程序运行时的调用关系 ) 实现函数作为参数 : 还要传递其环境所在的活动记录指针函数作为返回值 : 需要保存返回函数的活动记录静态形式张昱 : 程序设计语言理论编译技术回顾 19 张昱 : 程序设计语言理论编译技术回顾 20 闭包 Closures 函数值是一个元组 closure = <env, code> 当调用用闭包表示的函数时为调用分配活动记录按闭包中的环境指针 env 来设置活动记录中的访问链张昱 : 程序设计语言理论编译技术回顾 21 示例 : 基于静态作用域时 procedure ; begin r := 0.12; end; begin ; small; writeln; ; small; writeln 在中定义, 中访问的 r 是中定义的执行后 : end. 张昱 : 程序设计语言理论编译技术回顾 22 示例 : 基于动态作用域时 procedure ; begin r := 0.12; end; begin ; small; writeln; ; small; writeln 执行后 : 中调用的所访问的 r 是中定义的 ; small 中调用的所访问的 r 是 small 中定义的 end. 张昱 : 程序设计语言理论编译技术回顾 23 动态作用域使用动态作用域的语言 Pascal Emacs Lisp Common Lisp( 兼有静态作用域 ) Perl( 兼有静态作用域 ) Shell 语言 (bash, dash, PowerShell) 其他宏展开张昱 : 程序设计语言理论编译技术回顾 24 4

5 实现动态作用域的方法深访问用控制链搜索运行栈, 寻找包含该非局部名字的第一个活动记录浅访问为每个名字在静态分配的存储空间中保存它的当前值当过程 p 的新活动出现时,p 的局部名字 n 使用在静态数据区分配给 n 的存储单元 n 的先前值保存在 p 的活动记录中, 当 p 的活动结束时再恢复张昱 : 程序设计语言理论编译技术回顾 2 procedure ; begin r := 0.12; end; ; small; writeln; ; small; writeln end. 张昱 : 程序设计语言理论编译技术回顾 26 procedure ; begin r := 0.12; end; ; small; writeln; ; small; writeln end. 张昱 : 程序设计语言理论编译技术回顾 2 procedure ; begin r := 0.12; end; ; small; writeln; ; small; writeln end. 张昱 : 程序设计语言理论编译技术回顾 28 procedure ; begin r := 0.12; end; ; small; writeln; ; small; writeln small 0.2 end. 张昱 : 程序设计语言理论编译技术回顾 29 procedure ; begin r := 0.12; end; ; small; writeln; ; small; writeln r 0.12 small 0.2 end. 张昱 : 程序设计语言理论编译技术回顾 30

6 procedure ; 静态区 begin r := 0.12; end; 使用值的地方 ; small; writeln; ; small; writeln 3. 抽象机模型栈型机器 (Stack Machines) 寄存器机器 (Register Machines) end. 张昱 : 程序设计语言理论编译技术回顾 31 栈型机器栈型机器模型是一种简单的求值模型没有变量和寄存器中间结果存放在栈中每条指令 : 1) 从栈顶取操作数 2) 将这些操作数从栈中删除 3) 在这些操作数上计算所需要的操作 4) 将结果入栈栈型机器操作示例例在栈型机器上执行加法操作 9 9 pop add 12 9 push 张昱 : 程序设计语言理论编译技术回顾 33 张昱 : 程序设计语言理论编译技术回顾 34 栈型机器操作示例指令 push i 将 i 置于栈顶 add 从栈中弹出两个元素, 将它们相加, 再将结果入栈计算 + 的程序 push push add Java 字节码.Net 的 CLR Pascal 的 P-code Perl 属于此栈型机器的优点统一的编译机制 => 编译器实现简单每个操作从同一地方取操作数, 并把结果放到同一地方操作数的位置是隐式的总是在栈顶无需显式指定操作数和结果的位置代码量小程序更紧凑如, 用 add, 而不是 add r1, r2 Java 字节码使用栈求值模型的原因张昱 : 程序设计语言理论编译技术回顾 3 张昱 : 程序设计语言理论编译技术回顾 36 6

7 栈型机器的优化存在的问题 add 指令涉及 3 条访存操作 :2 reads 1write 栈顶被频繁访问优化思路将栈顶内容保存在寄存器中 ( 寄存器访问速度快 ) 累加器 (accumulator) add 指令改为 acc acc + top_of_stack 这样就只有一条访存指令了带累加器的栈型机器不变式 (invariants) 表达式的结果总是在累加器中 op(e 1,, e n ): 在计算 e 1,, e n-1 后, 将累加器的值入栈表达式值保存在栈中计算 + acc 12 stack acc push acc acc acc acc + top_of_stack pop 张昱 : 程序设计语言理论编译技术回顾 3 张昱 : 程序设计语言理论编译技术回顾 38 寄存器型机器寄存器型机器模型操作数保存在寄存器上指令中需要参数指定操作数的地址, 如 add t1, t2, t3 如,Dalvik VM Lua VM Parrot VM 等均属于此类相比栈型机器的优势和劣势劣势 : 编译器复杂 ( 寄存器分配和指派等跟踪变量存放的场所 ) 代码量大单条指令的代价高优势 : 指令数少 ( 执行得快 ) 还可以做一些栈型机器无法实现的优化 ( 如公共表达式的结果保存到寄存器中, 不必重复计算 ) 张昱 : 程序设计语言理论编译技术回顾 39 栈 vs. 寄存器栈代码容易翻译到寄存器代码, 反之则不成立局部变量直接映射栈存储单元映射到虚拟寄存器栈代码 iload 4 bipush iadd istore 6 iload 6 ifreq 寄存器代码 imove r10, r4 biload r11, iadd r10, r10, r11 imove r6, r10 imove r10, r6 ifreq r10, 说明 ; 加载局部变量 4 ; 加载立即数 ; 整数加 ; 存储结果到局部变量 6 ; 加载局部变量 6 ; 如果结果为 0, 跳到张昱 : 程序设计语言理论编译技术回顾 40

PowerPoint Presentation

PowerPoint Presentation 引论编译原理和技术张昱 0551-63603804,yuzhang@ustc.edu.cn 中国科学技术大学计算机科学与技术学院主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 2 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 :