第九章 目标代码生成.

Slides:



Advertisements
Similar presentations
颐高集团项目中心 海亮地产开发模式研究报告. 目 录 目 录 第四部分:海亮地产高周转模式执行 第二部分:海亮地产高周转模式原因 第三部分:海亮地产高周转模式内涵 第一部分:海亮地产企业背景 第五部分:海亮地产高周转支撑体系.
Advertisements

足太阴脾经在足大趾与足阳明胃经衔接, 在胸部与手少阴心经相接。 联系的脏腑器官有 咽、舌,属脾,络胃,注心中。 络脉从本经分出,走向足阳明经,进入腹腔,联络肠胃。 经别结于咽,贯舌本。 经筋结于髀,聚于阴器,上腹,结于脐,散于胸中。 第四章 足太阴经络与腧穴 第一节 足太阴经络.
创作计算机程序 学习目标: 定义术语 “ 计算机程序 ” 说明编程过程中流程图和伪代码的用途 介绍程序在寻求解决方案的过程中可以利用的两种方 法 区别计算机编程的两个主要步骤 列举并描述面向对象编程的三个要素.
人的性别遗传 合肥市第四十九中学 丁 艳. 男女成对染色体排序图 1 、男性和女性各 23 对染色体有何异同 ? 哪 一对被称为性染色体 ? 2 、这两幅图中,哪幅 图显示的是男性的染色 体?哪幅图显示的是女 性染色体? 3 、图中哪条染色体是 Y 染色体?它与 X 染色体 在形态上的主要区别是.
1 主題三 網路常見衝突事件 的防範 3-1 認識網路兩性交往常見的衝突事件 3-2 瞭解處理兩性網路交往衝突之注意事項 3-3 認識處理兩性網路交往常見的衝突事件的 有效方法 有效方法.
平面构成 第六章 平面构成形式与法则 — 破规与变异. 第七章 平面构成形式与法则 — 破规与变异 破规与变异构成的形式、有下列四类: 一、特异构成 特异构成。其表现特征是,在普遍相同性质的事物 当中,有个别异质性的事物,便会立即显现出来。
我的未来不是梦 攀枝花市经贸旅游学校. 1. 文中案例王萍苦恼的原因是 什么? 2. 你有哪些办法可以帮助王萍? 导入 思考  谁来帮帮她?
泛黄的春联还残留在墙上 依稀可见几个字岁岁平安 在我没回去过的老家米缸 爷爷用楷书写一个满 黄金葛爬满了雕花的门窗 夕阳斜斜映在斑驳的砖墙 铺着榉木板的屋内还弥漫 姥姥当年酿的豆瓣酱 我对着黑白照片开始想像 爸和妈当年的模样 说着一口吴侬软语的姑娘缓缓走过外滩 消失的旧时光一九四三 在回忆的路上时间变好慢.
南山中學 102學年度 性別平等教育週性別教育 性騷擾防治.
103年度學生健康檢查.
1、一般地说,在生物的体细胞中, 和 都是成对存在的。
辨性别 A B. 辨性别 A B 第三节人类染色体与性别决定 昌邑市龙池初中 杨伟红 学习目标 1.理解人的染色体组成和传递规律。 2.解释人类性别决定的原理。 3.通过探究活动,解读数据了解生男生女的比例。
未成年少女墮胎的法律問題.
台灣科技之父 李國鼎 先生.
LOGO 海龜樂園 編寫程式入門 第一節 圖龜編程 中二級電腦科.
報告人 方萱玉 100上學期教學組業務報告.
建構 Beta電腦 – Fall /29/0.
系统简介 理财顾问 业务 是基于通信平台的技术优势,整合《理财周刊》、第一理财网、乾隆集团等合作伙伴提供的理财产品内容和权威的理财专家资源,以集中式呼叫中心为主的服务方式,让普通百姓可以享受到快捷、全面、专业、权威的资讯及投资理财的服务平台。
4.3 分页式存储管理 分页式存储管理的基本原理 相联存储器和快表 分页式存储空间的分配和去配
南通房地产市场监测周报 彤心策划·市场研究部出品——
专题三 生物圈中的绿色植物.
Chapter 12 護照簽證. Chapter 12 護照簽證 第一節 護照未辦妥 辦理護照需要當事人照片二張、身份證正本,辦理時間通常需要5個工作天。旅行社因作業人員疏失,延宕辦理時效,致旅客無法如期出國,應負損害賠償責任。
第 2 章 生物的遺傳 2-1 基因與遺傳 2-2 細胞分裂 2-3 遺傳法則 2-4 突變 2-5 生物科技.
宦官那些事儿 宦官那些事儿 主讲:小学部李永善 主讲:小学部李永善.
D、結構化技術 主要的結構化技術 結構化程式設計 (Structured Programming)
揭秘 庄家 股市中的 为什么你的股票一买就跌,一卖就涨? 为什么出了利好,股价反而下跌? 为什么有的股票一直涨停?
电视教育课 【5】 小学生行为习惯养成教育.
第六章 中间代码生成 赵建华 南京大学计算机系.
1.1.2 四 种 命 题.
2006年台灣醫學中心大搜查 聰明病人 完全就醫指南.
色 弱 與 色 盲.
宁波爱地房产市场年报 郊五区
入库验收 讲课人:卢玉娟 《仓储管理》.
大连理工大学软件学院 软件工程系 赖晓晨 计算机组成与结构 大连理工大学软件学院 软件工程系 赖晓晨
宠物之家 我的宠物性别? 雌(♀) or 雄(♂) 第一阶段:我的宠物我做主 第二阶段:宠物“相亲记” 第三阶段:家族诞生
第七章 控制器 7.1 控制器的组成及指令的执行 7.2 控制方式和时序的产生 7.3 微程序控制器 7.4 微程序控制器及其微程序设计举例
乳猪断奶后拉稀,掉膘与教槽料.
8051 指令.
第4章 处理器(CPU) 4.1 引言 4.2 逻辑设计的一般方法 4.3 建立数据通路 4.4 一个简单的实现机制 4.5 多周期实现机制.
第5章 语义分析(Semantic Analysis)
编译原理与技术 词法分析(1) 2018/11/28 《编译原理与技术》讲义.
6 下标变量的中间代码生成 下标:数组;变量: 下标变量:即数组分量: 简单变量:id,其地址可查到;
第2章 计算机指令集结构 曲冠南
一个非常简单的CPU的设计 1、组合逻辑控制器 2、微程序控制器.
新觀念的 VB6 教本 第七章 讓程式轉彎的控制敘述.
计算机原理及系统结构 第十八讲 主讲教师:赵宏伟                 学时:64.
电子元器件基础 贵州电子信息职业技术学院 谢忠福.
陳慶瀚 機器智慧與自動化技術(MIAT)實驗室 國立中央大學資工系 2013年5月28日
第五章 C/C++及汇编语言的混合编程 5.1 ARM C/C++编译器 5.2 在C/C++程序中内嵌汇编指令
第六章 空 间 力 系.
條件處理.
編譯程式設計 期末專題說明 V1.1 May 2004.
语义分析概述 符号表 第六章 语义分析.
永宏PLC --FB-PLC【基礎功能篇 】
第六章 中间代码生成 主要内容 常见的中间代码结构 语法制导方法概论 四元式中间代码生成过程.
编译原理实践 11.语义分析与代码生成.
Week 2: 程式設計概念與 演算法的效能評估
陳維魁 博士 儒林圖書公司 第三章 變數與繫結 陳維魁 博士 儒林圖書公司.
考前总结 背景 必要性 作用 新旧版交替面临一些问题 从教学目标和要求说起 知识梳理 可能有助于提高考试成绩 或者让知识掌握得更好.
2019/4/29 计算机组成原理 辅导教师:陆明强.
機器語言, 組合語言, 與編譯器 參考: β 文件; 實驗 #5B; C 語言講議 當我在我的程式碼中發現一堆 麻煩時, 朋友和同事跟我說了
開放電腦計劃 報告人:陳鍾誠 2011 年 8 月 20 日 台灣開源人年會 COSCUP 2011 – 中研院
代码优化.
第十章 优化 网上教学系统: : 编译原理 第十章 优化 网上教学系统: : 编译原理.
美麗的西子湖.
第九章 运行时存储空间组织 网上教学系统: : 编译原理
夏昊珺 PB 体系结构习题课2 夏昊珺 PB
1.3操作系统提供的服务和用户接口 操作系统提供的用户接口 程序接口与系统调用 操作接口与系统程序
04-0 第 4 章 轴 测 图 4.1 轴测图的基本知识 4.2 正等轴测图 4.3 斜二测图.
判斷(選擇性敘述) if if else else if 條件運算子.
Presentation transcript:

第九章 目标代码生成

1. 目标代码介绍 实际目标代码:实际机器上的指令序列 绝对地址机器代码:编译后能够立即执行的机器语言代码,代码中所有地址均已定位。 可重定位的机器代码:当程序执行时,必须由连接装入程序把它们和一些运行时子程序连接起来,转换成可立即执行的机器语言代码。 汇编代码:汇编语言代码必须经过汇编程序汇编,将其转换成可执行的机器语言代码。 虚拟目标代码:虚拟机上的目标程序。 在本地机器上具备虚拟机的解释器。 顾名思义,目标程序的生成和目标机是密切相关联的,也就是说目标机的结构、能力会直接影响我们生成目标程序的难易程度和质量。在实际中也有很多程序设计语言他们的编译过程并不是直接对具体的目标机生成目标代码,而是产生到一种类似于汇编的虚拟目标机上,然后由虚拟目标机的虚拟指令到具体目标机的转换。比方说以前的p4pascal,他生成的就是叫做Z语言的虚拟指令系统,由z语言的程序到具体目标机进行转换,类似的情形有现在的java语言,他编译完了是到一个中间语言的形式,然后利用相对应的解释程序往不同的目标机进行解释和执行。我们这里要考虑的就是把四元式的结构映射到某个目标机上,由于我们现在考虑的对象中,目标机没有一个具体的目标机,所以我们这里考虑的结构也是一个虚拟的目标机

2 虚拟机的寻址方式 寻址方式 汇编形式 意义 绝对地址 A A存储单元内容 寄存器 R R 寄存器内容 变址 C(R) (C+R)地址内容 间接寄存器 *R (寄存器内存放的是操作数的地址) R所指向地址内容 间接变址 *C(R) (C+R)所指向地址内容 立即数 C 常数C

虚拟目标机 假定虚拟的目标机按字编址,每个机器字存放一条指令。指令的格式为: OP destination,source 其中OP为操作码,source 和destination分别为源操作数和目的操作数。 source 和destination可以是立即数C、寄存器R、存储字地址A(绝对地址或以及以寻址方式表示的地址),但不能同时为存储字地址。

虚拟目标机的指令系统 指令名称 指令形式 读 IN R 除 DIV R, A 写 OUT R 条件真转移 JMPT R, A 取值 LD R, A 条件假转移 JMPF R, A 存值 ST A, R 无条件转移 JMP A 加 ADD R, A 取址 LEA R, A 减 SUB R, A 块传送 MOVEB addr1, addr2, size 乘 MULT R, A 现在输入的是四元式的结构,我们如何把四元式转换成我们的目标指令,大家可能会看出,这个虚拟的目标指令和实际的汇编指令在一定程度上可能会有点差别,比方说*/运算 在某些语言中可能不是直接提供的,可能通过一个宏汇编或者是其他方式来是实现的,我们这里就是假定其具有这样的一个形式,这样操作起来就方便 若目标机指令集中有“自增”指令INC,就可以被高效地翻译为一条指令:INC a ;否则,按照前面的模式将被翻译为指令序列: LD R , a ADD R , 1 ST a , R

虚拟目标机的寄存器 寄存器是CPU内部的元件,寄存器拥有非常高的读写速度 ,它们可用来暂存指令、数据和地址。 寄存器种类:累加器、变址器、通用寄存器等等。 在虚拟目标机中,取出几个寄存器作为地址计算专用的寄存器分别为SP、TOP、GP;其他寄存器用R1、R2…表示。 在一般的目标机还需要考虑的问题就是寄存器的问题,你的目标机中有哪些通用的寄存器,哪些可以作为累加器,哪些作为变址器等等,我们这里也做这样一个假设,我们取出几个寄存器作为地址计算专用的寄存器,比方说我取3个寄存器,一个用sp表示,这个是我们在程序运行时,存储空间当前活动记录的首地址,也就是调用链活动记录的首地址,用top寄存器表示第一个可用的存储单元的地址,这两个寄存器指针实际上在我们前面的介绍中已经说清楚了他的用途,另外我们可以选择一个特殊的寄存器,比方说用SP0表示,记录我们静态存储区的首地址,因为我们知道在程序中有很多的静态变量,这些都分配在程序的静态区,他们的地址计算以后是由SP0+偏移量 就计算出他的偏移地址,这是3个寄存器我们拿出来作为专用寄存器,其他可用寄存器我们用r1 r2 。。rn来表示,这是我们虚拟目标机假设的一种形式,下面要考虑的是输入一组四元式,怎么样把他生成目标指令。

四元式到目标代码的翻译 (一个通用寄存器R,且不考虑效率) 表达式四元式的翻译 赋值语句四元式的翻译 输入输出语句四元式的翻译 条件语句四元式的翻译 循环语句四元式的翻译 过程、函数说明语句四元式的翻译 过程、函数调用语句四元式的翻译

从抽象地址到目标地址 (C语言) x目标代码 简写 x抽象地址形式 off[gp] * off[gp] (off)[sp] (0, off, dir) (0, off, indir) (1, off, dir) (1, off, indir) (-1, off, dir) (-1, off, indir) off[gp] * off[gp] (off)[sp] *(off)[sp] (off)[sp] *(off)[sp]

3.1 表达式四元式的翻译 LD R,X/*X ;把X值或X指向的地址中的值取到R中 运算型四元式(OP,X,Y,t) 对应生成3条指令 LD R,X/*X ;把X值或X指向的地址中的值取到R中 Op R,Y/*Y ;根据运算符生成对应指令,结果存入R ST t,R ;将R内容存入临时变量单元t中 两点重要的解释: 目标指令中X,Y,t对应的一个具体的地址,如(offx)[sp] 如果XY为间接变量,这里的寻址方式为间接,用*X表示,对应的具体地址为 *(offx)[sp]或*(offx)[gp] 。 我们下面就来考虑每一种四元式他是如何生成目标指令的翻译, 运算型四元式:运算符 两个运算分量 结果是t,假如他是一个双目运算,一般我们就生成3条指令,1、把x取到r中,2运算型指令,根据运算符对应的运算生成对应的指令比方说add r y,sub r y这样的运算,3就是一个存运算,把r中的内容存到t中,st r t1.对于一个运算型的四元式我就生成这样三条指令就可以完成这样一个任务。这里需要解释的有两点,1我们用x和y表示变量,我们在介绍中间代码的时候说,这个x和y是指向符号表中的地址,是一个指针,他的抽象地址是在符号表中,生成目标指令的时候这个地方他实际上生成的是一个具体的地址,比方说sp+xoff 类似于这样一种形式,在目标代码这里就是一个具体的地址,为了让大家看起来方便,我们还是用x表示他,其实这里已经应该是地址的形式,就是sp+偏移来表示,如果不是本层的,就按照我们上次课介绍的就是sp+display[L]+off,第二个问题,如果说x或者y是间接变量的话,我们这里的寻址方式就应该是间接的寻址方式,比方说x是间接变量,那就用*x表示他是一个间接的寻址方式。(复述一下,x y t1实际上写的都是变换后的地址,如果是间接变量,用间接寻址方式),后面的讲解过程中由于考虑到方便性和可读性,我们还是采用xy这种形式而不是sp+off。第一类运算型的四元式我们就这样生成

3.2 赋值语句四元式的翻译 赋值型的四元式: (:=,right,-,left) 生成的目标指令是两条 3.2 赋值语句四元式的翻译 赋值型的四元式: (:=,right,-,left) 生成的目标指令是两条 LD R, right/*right ;把right值取到寄存器中 ST left/*left,R ; 把寄存器中内容存到left中 注意的问题和前面是一样的。

3.3 输入输出语句四元式的翻译 输入语句四元式的一般形式为: (READ,_ , _ , A ) 3.3 输入输出语句四元式的翻译 输入语句四元式的一般形式为: (READ,_ , _ , A ) 表示将一个外部值读入到变量A中,则目标代码为: IN R ; ST A,R 输出语句的四元式形式一般为: (WRITE,A , _ , _ ) 表示将变量A的值输出,它生成的目标代码为: LD R,A; OUT R 第三类是输入输出四元式,输入四元式一般是read,x 这对应的目标指令是两条,1、in R,把外部的数据输入到R中,ST R x,把r中的存到x中去。 输出四元式时write x,我们把x的值取到R中,再用输出命令输出出去,第一条是取ld r x;out,R,这就是我们输入输出指令的翻译。

3.4 条件语句四元式的翻译 if E then S1 else S2中间代码结构: E 的中间代码,结果-> t 3.4 条件语句四元式的翻译 if E then S1 else S2中间代码结构: E 的中间代码,结果-> t ( THEN , t , — , — ) S1 的中间代码 (ELSE , — , — , — ) S2 的中间代码 (ENDIF , — , — , — ) E目标代码,结果->t LD R, t JMPF R, 地址? S1目标代码 JMP 地址? S2目标代码

四元式等价的转换成目标指令需要用到两个栈 标号定位栈L1:定位性标号是为了某些转移提供地址的,需要把暂时没用到的标号存在栈中,例如while四元式可以对应一个嵌套的循环,在定位产生时还没产生跳转指令,它的地址还没用到,为了让后面能用到需要用栈把标号保存下来 目标指令地址栈L2:在有些产生跳转指令的时候,转移地址暂时无法确定,例如do四元式,不知道后面的转移地址,则把当前目标指令地址存到栈里,在知道转移地址以后,回填这个指令地址。回填地址是编译中的一项非常重要的技术 在我们的生成过程中,我们首先考虑的是单寄存器的情形,如果单寄存器的目标程序都可以完成的话,那你有多个寄存器的目标程序的完成应该是没有任何问题的,所以我们考虑单寄存器的情况,在不考虑优化的情况下,我们看怎么样吧四元式等价的转化成目标指令(重复,不考虑效率,怎么样等价的翻译),在能够翻译过去之后,我们再考虑如何来提高目标程序的质量,如何来评价这些目标指令。四元式如何翻译,在翻译的过程之中,我们用到两个栈,第一个是标号定位的栈,有些定位性标号是为了某些转移提供地址的,我们把没有用到的标号存在栈中,比方说while四元式可能是由嵌套的,在你定位产生的时候,还没产生跳转指令,他的地址还没用到,为了让后面能用到,我们就把他保存下来,由于循环可能是嵌套的所以我们用栈来保存。用L1来表示,第二个栈在有些产生跳转至零的时候,我们不知道后面的转移地址,比方说do四元式,我们不知道后面的转移地址,我们就要把这个指令地址存到栈里,以后知道转移地址以后,我们需要回填这个指令地址。这是编译中的一项非常重要的技术,就是回填地址的技术。 这是两个栈,

条件语句四元式的翻译 if E then S1 else S2中间代码结构: E 的中间代码,结果-> t ( THEN , t , — , — ) S1 的中间代码 (ELSE , — , — , — ) S2 的中间代码 (ENDIF , — , — , — ) E目标代码,结果->t [n] LD R,t; [n+1] JMPF R, *,并把该指令地址n+1压入L2栈 S1目标代码 地址回填,从L2栈中取出指令,改为 [n+1] JMPF R, m+1 [m] JMP *,并将m压入L2栈 S2目标代码 地址回填,从L2栈中取出指令,改为 [m] JMP (当前指令地址),ENDIF不生成指令

3.5 While语句四元式的翻译 While语句形式为: <S> → while <E> do <S> 结果->t (DO, t,—,—) S的中间代码 (ENDWHILE,—,—,—) while起定位作用,不生成目标代码,只是把当前目标地址n压入标号栈L1 E目标代码,结果->t [m] LD X, R; [m+1] JMPF R, * ,并把m+1压入L2栈,等待地址回填 S1目标代码 [k] JMP L1(top); L1出栈 地址回填L2代码:JMPF R,k+1 L2栈顶出栈

3.6 标号语句和goto语句的四元式翻译 标号定位语句的一般形式为: L: 语句 它所对应的四元式为: (LABEL , _ , _ , LLi ) 该四元式不产生目标代码,只需向L所分配到的存储单元LLi写入转向地址。设当前可用地址为A,则将地址A写入L所分配到的存储单元LLi .

goto语句的一般形式为: goto L 它所对应的四元式为: ( JMP , _ , _ , LLi ) 它所生成的目标代码为: JMP *LLi

入口四元式不产生任何指令,而是把当前指令地址填入函数信息表中。 3.7 过程、函数说明语句四元式的翻译 过程函数声明部分的四元式处理: (ENTRY, Q,-,-) 入口四元式不产生任何指令,而是把当前指令地址填入函数信息表中。 Name TypePtr Kind Level off Parm Class Code Size Forward 过程函数声明部分的四元式处理,这里有两个entry,Q ; q过程的入口四元式,endfunc,过程结束的四元式。入口四元式可以不产生任何的指令,但是需要做的工作是什么?需要把当前的指令地址,存到Q的过程函数信息表中的入口项,大家可以回忆一下每一个函数或者过程他的信息表中含有很多的信息,其中有一项就是函数的入口地址,这个入口是什么时候填?就是我们处理到entry这条指令的时候,我们就需要把当前的指令地址填到函数信息表中~。这是当前四元式需要完成的翻译工作。

3.7 过程、函数说明语句四元式的翻译 过程函数声明部分的四元式处理: (ENDFUNC, -,-,-) 3.7 过程、函数说明语句四元式的翻译 过程函数声明部分的四元式处理: (ENDFUNC, -,-,-) 1:生成一组读取命令,即恢复寄存器的现场信息 2:作废当前的活动记录,由两个指令完成,把当前的sp存给top,把动态链指针存给sp ST top , sp ; LD sp , 0(top) 3:产生一条返回指令,根据返回地址生成一个跳转指令。 JMP 1(top) *设过程活动记录首单元存动态链指针、第二个单元存返回地址 对于函数过程结束四元式,我们要做3类工作;1:生成一组取命令,即恢复寄存器的现场信息,我们知道在过程活动记录中有一块存储区,存的是现场信息,把寄存器中的值存到这里来了,现在函数已经结束了要返回,就要把这些信息恢复回去,有若干条取寄存器指令的动作。由于目标机不一样,所以保存的寄存器数量多少,我们也不好确定,所以我们就不具体写了,但是大家知道他们是由一组取命令完成的就可以了。2:由于函数已经结束了,我们就要把当前的活动记录作废掉,也就是在栈区把栈顶元素去掉,实际上是由两个指令完成的,把sp和top两个指针挪一下位置就可以了,把当前的sp存给top,把老的sp传给sp,也就是当前活动记录中动态链指针那一项传个sp。由于我们对两个指针进行了调整,就相当于我们把这个活动记录推掉了,现在sp值的是当前的活动记录。3:我们产生一条返回指令,根据之前存的返回地址我们要生成一个跳转指令。问题是sp和top都挪下来了,这个返回地址怎么找呢?~原来是sp+1,现在是top+1就可以了。我们就产生一个jump 【top+1】,这样我们就把这个翻译工作做完了。

3.8 过程和函数调用语句四元式的翻译 (保留符号表至目标代码生成部分) 3.8 过程和函数调用语句四元式的翻译 (保留符号表至目标代码生成部分) 函数调用四元式的处理: 值参四元式( ValACT , t , Offset , size ) 若t为间接变量,则生成的目标代码为: LD R , * t ;ST Offset(top) , R b. 若t 为直接变量,则生成的目标代码为: LD R , t ; ST Offset(top) , R c.若t 为数组,则生成成组传送的目标代码: MOVEB t , Offset(top) , size 函数调用四元式的处理,分成两块,一个是传参数的四元式, 一个是call四元式。注意的问题是参数传递有值引用和地址引用,一个传值 一个传地址,还有实参是直接变量还是间接变量, 在调用之前我们需要把活动记录栈里面压一个新的活动记录,实际上这部分工作也可以在入口四元式上进行处理,在哪处理时间效率上是一样的,但是可能一个函数被调用多次的话,重复代码就多一些。

过程和函数调用语句四元式的翻译 函数调用四元式的处理: 变参四元式( VarACT , t , Offset , size ) a. 若t为直接变量,则生成的目标代码为: LEA R , t ST offset(top) , R b. 若t为间接变量,则生成的目标代码为: LD R , t

过程和函数调用语句四元式的翻译 函数调用四元式的处理: ( CALL , f, true , [ Result ] ) 1. 生成填写变量访问环境指令 2. 把机器状态(寄存器内容)保存到活动记录的机器状态区中,一般应生成一组存的指令 3. 要填写管理信息.首先填写过程层数.从过程f的语义信息中取其层数,填入到3(top)中,生成指令为 LD R , sem[f].level ST 3(top), R 临时变量区 局部变量区 形参区 变量访问环境 活动记录大小 寄存器状态 过程层数 返回值 返回地址 动态链指针

过程和函数调用语句四元式的翻译 4. 填写动态链指针 ST 0(top), sp 5. 填写返回地址 [A] LD R, A+5 [A+1] ST 1(top), R 6. 生成过程活动记录 [A+2] ST sp, top [A+3] ST top, top + sem[f].size 7. 生成转向过程f入口的指令 [A+4] JMP sem[f].code 8. 若是函数调用,则把函数值读到寄存器中 [A+5] LD R , 2(top) [A+6] ST t , R 临时变量区 局部变量区 形参区 变量访问环境 活动记录大小 寄存器状态 过程层数 返回值 返回地址 动态链指针

对目标程序的评价 每条指令对内存的访问次数总和决定了目标程序的执行效率。 多利用寄存器中的资源可以达到减少访问内存的效果。 生成了这个目标程序之后可能会有一个评价,什么样的目标程序效率比较高,我们现在的目标程序基本上是按照用户源程序的程序结构过来的,所以程序结构是没有变化的,每条指令的访问内存次数的多与少就决定了我们目标程序的执行效率,我们给他做一个评价标准,比如一条指令,我们给他定义一个指令的执行代价,所谓xx的代价,就是他访问内存的次数,就定义成他的执行代价。访问内存是需要花时间的,访问内存的次数越多,执行效率就越慢。比方说间接寻址,我是先访问一次内存,取出单元的内容作为地址,再访问一次内存,这样的话他的指令代价可能更高。所以评价一个目标程序他的效率,就看他的整个程序的指令带价的总和,作为我们评价的标准。 另外在我们的处理过程中,可能还有一些注意的问题。能够不往内存中存取,是最好的。他在寄存器中,我们尽量不把他存到内存,不从内存中取值,特别是多寄存器的情形。大家看,x+y+z,取x,到r r+y就还到r 然后r+z就可以了,不用把x+y的结果存到t1,这样的话可以减少指令 提高程序的效率。;通过我们一些运算的结果占用在寄存器里,不用往内存中存,利用在寄存器中的资源,达到减少访问内存的效果,特殊情形可能还有问题,比方说目标代码的优化和带副本的优化。因为有些变量如果是间接变量,或者是往间接变量中存一个值,可能会改变寄存器中某一个变量的值,这种时候大家千万小心,这种时候就需要把寄存器中的值存回去,否则就可能会发生错误。

4 多寄存器的分配 名字 状态 变量名 R1 0/1 X 为了产生更高效的目标代码,合理利用寄存器资源,需要构造一个寄存器状态表: 当需要用到一个寄存器时,可以用一个函数查找寄存器表,检查是否存在空闲寄存器,若存在,则将空闲的寄存器分配,然后按存取计算操作来操作,同时把相应的寄存器的状态和占用者记录在寄存器状态表 刚才我们考虑的都是单寄存器不考虑执行效率然后我们生成了相应的目标代码,现在我们考虑多寄存器的情况,实际上单寄存器能够完成,多寄存器就一定能够完成,只不过我们希望他能够产生更高效的目标程序,假定我们有8个通用寄存器是可以使用的,为了达到合理的利用寄存器的资源,我们要构造一个寄存器的状态表,状态表中应该有这样几项,名字、状态 0 表示空闲1表示占用,占用该寄存器的变量的名字,以后再处理的时候我们就没有必要像原来取出一个变量,用完以后要马上存回到内存中去,现在因为我们有多个寄存器,可能还有更空闲的寄存器,所以我们不用急于把占用的寄存器倒出来,当我们需要用到一个寄存器的时候,我们可以用一个函数到寄存器表中去查一下,看看有没有空闲的寄存器,把空闲的寄存器分配给他,然后按我们以前的存取计算操作来操作,把相应的寄存器的状态和占用者记录在这个表里就可以了,

多寄存器的分配 当所有寄存器都被占用时,涉及到寄存器的剥夺问题。剥夺算法优劣会影响目标程序的执行效率。 对寄存器的剥夺是把寄存器中的内容存入内存中。 理论上的最优是最远使用点方法,实现困难 局部最优是基本块内最远使用点方法 问题是当我们查找寄存器状态表的时候,发现所有的寄存器都被占用了,怎么办,这就涉及到一个寄存器的剥夺的问题,剥夺哪一个寄存器?这种剥夺的算法可能会影响到我们的执行效率。这种处理就类似于操作系统中页式存储管理淘汰页的情形,把哪一个页面淘汰出去,我们这里相当于说把哪个寄存器存到内存中去,按照淘汰页的算法,实际上有一个最佳算法,在最远使用点的先淘汰,但是我们说后面的程序执行情况我们是没法判定的,因此这个是做不到的,但是我们处理四元式的时候我们曾经把他划分成很多个基本快,由于基本块里面的程序都是顺序执行的,因此在基本快内,我是可以找到最远使用点的,淘汰算法就可以按照最远使用点的先淘汰,特殊情况就是最远使用点都不在这个基本快里。比方说x123,都不在基本块里,只好随机的淘汰一个就可以了,这样做可以达到局部最优,但是未必能达到全局最优。所以每结束一个基本块的时候,我们需要把寄存器中的所有内容,都存到对应的内存中去,把所有的寄存器都倒出来,这样多寄存器我们就可以实现了,达到一个寄存器分配的目的。

总结 目标程序的生成要考虑的问题: 目标机的具体形式 如何把四元式翻译成目标程序 优化,如何高效的生成目标代码。 要注意的问题: 符号表一直存在到目标代码生成,目标代码生成之后没有符号表,运行的只是目标程序。 总的来说,目标代码生成要想做优化工作还有很多,我们限于时间的关系,没讲那么多。目标程序的生成,1、要考虑目标机的问题,2、如何把四元式翻译成目标程序 3、考虑优化的问题,如何高效的生成目标代码。需要跟大家解释的和前面连在一起的问题,要注意的问题,前面符号表一直存在的,到目标代码生成的过程中还一直存在,等我们生成了目标代码他的作用就没有了。因为我们把变量都换成地址了,把改取该用的内容都取出来了,过程的入口地址已经填上了,等到call的时候,我就到那里找到,生成目标指令就可以了。所以,在目标代码生成之后符号表就没用了,以后运行的就是目标程序了。

X = u*w/(u*l+1); Y = u*j/(X+k) X = u*w/(u*l+1); Y = u*j/(X+k) P183-4 试写出下述程序段的目标代码,其中变量均为非形参实型变量。 X = u*w/(u*l+1); Y = u*j/(X+k) ( MULTF,u,w,t1) (MULTF,u,l,t2) (ADDF, t2, 1,t3) (DIVF,t1,t3,t4) (ASSIG,t4,-,X) X = u*w/(u*l+1); ( MULTF,u,j,t5) (ADDF, X, k,t6) (DIVF,t5,t6,t7) (ASSIG,t7,2,Y) Y = u*j/(X+k)

LD R,u MULT R,w ST t1 , R LD R, u MULT R, l ST t2, R LD R, t2 ADD R, 1 ST t3, R LD R, t1 DIV R, t3 ST t4, R LD R, t4 ST X, R ( MULTF,u,w,t1) (MULTF,u,l,t2) (ADDF, t2, 1,t3) (DIVF,t1,t3,t4) (ASSIG,t4,-,X)

LD R,u MULT R,j ST t5 , R LD R, X ADD R, k ST t6, R LD R, t5 DIV R, t6 ST t7, R LD R, t7 ST Y, R ( MULTF,u,j,t5) (ADDF, X, k,t6) (DIVF,t5,t6,t7) (ASSIG,t7,-,Y)

例子P183-5 试写出下述程序段的目标代码,其中变量均为非形参实型变量。 while (x < y) { y = y + 1; if (y > 0) y = y-x; else while (y < 0) y = y + x; } 中间代码结构 (WHILE,-,-,-) (LT , x, y, t1) (DO,t1,-,-) (ADDF,y,1,t2) (ASSIG,t2,-,y) (GT , y, 0, t3) (THEN, t3,-,-) (SUBF,y,x,t4) (ASSIG,t4,-,y) (ELSE,-,-,-) (WHILE,-,-,-) (LT , y, 0, t5) (DO,t5,-,-) (ADDF,y,x,t6) (ASSIG,t6,2,y) (ENDWHILE , - ,- ,- ) (ENDIF,-,-,-) (ENDWHILE , -, - , -)

JMP *(33) 回填22至L2(top) L2(top)=21 目标代码 L1(top)=1 LD R,x LT R,y ST t1 , R LD R,t1 JMPF R, * (34) L2(top)=5 LD R,y ADD R,1 ST t2 , R LD R,t2 ST y , R GT R,0 ST t3 , R LD R,t3 JMP0 R,* (22) L2(top)=15 LD R,y SUB R,x ST t4 , R LD R,t4 ST y , R JMP *(33) 回填22至L2(top) L2(top)=21 L1(top)=22 LD R,y LT R,0 ST t5 , R LD R,t5 JMP0 R, *(33) L2(top)=26 LD R,y ADD R,x ST t6 , R LD R,t6 ST y , R JMP 22:L1(top) 回填33至L2(top) 回填33至L2(top) JMP 1:L1(top) 回填34至L2(top) while (x < y) { y = y + 1; if (y > 0) y = y-x; else while (y < 0) y = y + x; } 1