当前课程知识点:Compilers Techniques > 7 Code Generation > 7.4 A Simple Code Generator > 7.4 A Simple Code Generator
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课我们继续来学习代码生成
我们以之前用到的这段代码序列
作为一个例子
来学习一个基本的代码生成器
在没有搜集全局信息之前
我们暂且以基本块
作为我们的程序基本单元
来生成我们想要的代码
我们需要考虑的问题有如下几个
首先
我们需要依次去考虑
基本块当中的每条语句
为它来产生代码
假定三地值语句的每种算符
都有对应的目标机器算符
假设计算结果留在寄存器当中
尽可能长的时间
除非这个寄存器要用于其它的计算
或者基本块要进行结束
为此
我们在生成代码过程当中
需要记录一些基本的信息
比如说
对于a=b+c这样的语句来说
如果寄存器 Ri含有b的信息
Rj含有c的信息
并且b在此后不再活跃了
那么我们可以产生
ADD Rj, Ri
我们将a留在 Ri当中
如果Ri包含b的值
c在内存单元当中
b仍然不再活跃了
那么我们可以产生 ADD c, Ri
或者也可以产生 MOV c, Rj
ADD Rj, Ri
也就是我们根据不同的情况
来使用不同的寄存器
或者不同的语句序列
如果c的值以后
还要去使用的话
我们会发现第二种代码
是更为合适的
在代码生成的过程当中
我们需要去跟踪寄存器的内容
和它对应的名字的地址
寄存器需要记住哪些信息呢?
寄存器需要知道
当前的这一点
它所描述的所有的变量是哪一些
也就是寄存器
要保存若干个名字的值
它要一直知道
保存的是哪些名字的值
比如说b=a 在b=c这个语句之前
R0假设保存的是变量a的值
那么b=a这样的一条赋值
我们不用为这条语句
就是产生任何的指令
在这条语句之后
R0仍然保存变量a的值和变量b的值
在代码生成的过程当中
我们需要讨论的另一个问题是
名字的地址
它需要描述记住运行时每个名字的值
应该在什么地方去找到它
这个场所
可以是寄存器
也可以是栈的单元
或者内存的单元
甚至是它们的一个集合
比如说
我们在产生MOV c, R0之后
我们知道c的值
可能在R0中和c中
对应的存储单元找到
还有名字的地址信息
存放于符号表当中
另外我们需要建立寄存器来描述
对应的符号表
这两个描述
在代码生成过程当中
可能是变化的
我们再看一下,对一个三地址语句
x=y op z
我们可以调用一个函数
getreg来决定y op z计算的结果
存放的场所
假设是L
我们需要查看y的地址描述
确定y的值当前所对应的一个场所
我们写为y'
如果y的值不在L中
我们产生一个指令序列
MOV y', L
我们将y'移动到L中
然后我们产生对应的指令序列
op z', L
其中z'是z当前的场所之一
如果y和z或者是z当前的值
不再引用了
那么在块的出口
也不再活跃
并且还在寄存器当中
那么我们知道这个时候
可以去修改寄存器的描述
接下来如果y的值在R当中
这个R不含有其它名字的值
并且在执行x=y op z之后
y不再有下次引用
那么我们可以返回这个R作为L
否则如果有的话
我们可以返回一个空闲的寄存器
也就是去使用空闲的寄存器
否则如果x在块中
如果有下一次引用
或者op必须用寄存器的算符
那么我们需要找到
另外一个已经占用的寄存器R
去存放它的值
可能产生MOV R, M这样的指令
并且需要修改M的描述
否则
如果x在基本块中不再使用了
不再引用了
或者找不到适当的被占用的寄存器的话
我们只能选择x的内存单元作为L
我们再看一个赋值语句
假设d= (a-b)+ (a-c) + (a-c)
我们可以通过编译
得到它的三地址代码序列
也就是中间代码
t1=a-b
t1是临时变量
t2=a-c
t3=t1+t2
d=t3+t2
然后我们可以针对这个三地址代码序列
得到对应的汇编语句
我们来看一下
在最开始寄存器是空的
第一个语句t1=a-b
我们可以生成对应的代码
MOV a, R0
将A移动到R0中
R0中含有了a
然后SUB b, R0
我们从 a当中,也就是R0当中减去b
R0在此刻的状态是含有t1
然后第二行语句
t2=a-c
MOV a, R1
我们将a移动到R1中
然后SUB c , R1
我们用R1去减去c的值
此刻R0含有t1的值
R1含有t2的值
然后第三行语句
t3=t1+t2
我们可以产生对应的代码
ADD R1, R0
我们把R1加到R0之上
我们知道R0含t3的值
R1含有的是t2的值
最后一行语句d=t3+t2
我们产生的代码是ADD R1, R0
这个时候
R0含有的是d的值
在最后我们产生最后一行代码
MOV R0, d
我们再将R0移动到d当中
这样我们就将上述的赋值语句
变为我们想要的生成的代码
那么这个语句序列当中
我们还需要考虑的一些
额外的问题是
前三行指令
其实是可以修改的
使执行的代价变得更低
比如说在修改之前
是我们之前写好的语句
那么修改之后
可以将它变为 MOV a, R0
这一行跟原来是一样的
第二行
我们用了寄存器 MOV R0, R1
降低了这条指令的代价
然后我们再可以用 SUB b, R0
SUB c, R1
同样的,我们可以得到想要的结果
接下来我们需要考虑
为变址和指针产生代码的情况
变址和指针运算的三地址代码的处理
和二元运算符的处理
是一样的
我们接下来讨论一下条件语句
对于条件语句来说
需要实现条件转移
那么有两种方式
首先我们可以根据寄存器的值
来讨论是否为如下
我们所需要的6个条件之一
这6个条件是
负、零、正、非负、非零、非正
我们可以用条件码来表示
我们想要的计算的结果
或者装入寄存器的值是负的、
是零、还是正的
比如说
有这样的一个语句
if x小于Y goto z
那么需要进行一个条件的判断
我们把x-y的值
存入到寄存器R当中
然后来判断R的值是否为负
如果为负的话,我们跳转到z
我们把它写出来
if x小于y goto z
对应的实现就是CMP x, y
也就是比较 x和y来做一个减法
那么如果它的值是小于0的,跳转到z
接下来对于x=y+w
if x小于0 goto z
我们得到它对应的语句序列是
MOV y, R0
我们将y移动到R0中
ADD w, R0
将w累加到R0之上
MOV R0, x
我们再把R0移动到x
然后我们来比较x的值
是否为0
如果小于0
我们跳转到z
这小节就到这
谢谢大家
-1.1 Overview of Compilers Techniques
--Chapter 1 Overview of Compilers Techniques
--Overview of Compilers Techniques
-2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
-2.2 Regular form
--2.2 Regular form
-2.3 Finite automata
--2.3 Finite automata
-2.4 DFA construction, Subset construction, Simpleset DFA
--2.4 DFA construction, Subset construction, Simpleset DFA
-2.5 Lex
--2.5 Lex
-3.1 Context-free Grammars
--3.1.1 The Role of the Parser
--3.1.2 The Formal Definition of a Context-free Grammar
-3.2 Writing a Grammar
--3.2.1 Elimination of Left Recursion
--3.2 Top-Down Parsing
-3.3 Languages and Grammars
--3.3 Language and Grammars
-3.4 Top-Down Parsing
--3.4.3 Recursive Descent Analysis
--3.4.4 Nonrecursive Descent Analysis
-3.5 Bottom-up Parsing
--Bottom-up Parsing
-3.6 LR Parsing
--3.6.6 Characteristics of LR Parsing
--3.6.7 Non Ambiguous and Not LR Context-Free Grammars
-4.1 Syntax-Directed Definitions
--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes
--Syntax-Directed Definitions
-4.2 Bottom-Up Calculation of S Attribute
--4.2.1 Bottom-Up Calculation of S-Attributed
-4.3 L-Attributed Definitions
--4.3.1 L-Attributed Definitions
--4.3.3 Design of Predictive Translator
--L-Attributed Definitions
-4.4 Bottom-Up Parsing of L-Attributed Translation
--4.4.1 Bottom-Up Parsing of L-Attributed Translation
--4.4.2 Simulate the Parsing of Inherited Properties
--Bottom-Up Parsing of L-Attributed Translation
-5.1 Overview
--Overview
-5.2 Global Stack Storage
-5.3 Calling Sequences
-5.4 Non Local Names
--5.4 Non Local Names and dynamic scope
--Non Local Name
-6.1 Overview of Intermediate Code Generation
--6.1 Overview of Intermediate Code Generation
-6.2 Declaration Statements
-7.1 Issues in the Design of Code Generator
--7.1 Issues in the Design of Code Generator
-7.2 Target Machine
--Target Machine
-7.3 Basic Blocks and Flow Graphs
--7.3 Basic Blocks and Flow Graphs
-7.4 A Simple Code Generator
-8.1 Demonstration of Compiler Framework based on Python
--8.1 Demonstration of Compiler Framework based on Python
-8.2 Basic
--8.2.4 SA
-8.3 SimpleJava