当前课程知识点:Compilers Techniques > 7 Code Generation > 7.3 Basic Blocks and Flow Graphs > 7.3 Basic Blocks and Flow Graphs
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课我们继续来学习代码生成
我们来讨论基本块和流图
首先我们需要想一下
怎样为三地址序列
生成对应的目标代码
我们来看一个例子
针对这样的一段代码来说
里边包含着do while这样的循环
i作为一个变量
我们需要对它来控制整个循环的过程
我们看一下
它的三地址代码写在右侧
那么第一条语句
跟原来是一样的
把prod赋值为0
第二条语句i=1
从第三行语句开始
我们进入到循环的内部
一直到第12条语句
我们来进行判断条件
if i<= 20
我们跳转到(3)这个语句
我们观察到
这样的语句
是作为三地址代码出现的
首先是基本块的概念
一个基本块是指一个连续的语句序列
控制从它的开始进入,
从它的末尾离开
我们看到
整个的循环从3开始进入
在12这条语句离开
下一个概念是流图
我们使用有向边来表示
基本块之间的控制信息
就可以得到整个程序的流图
那么如何来划分基本块呢
首先我们需要确定所有的入口语句
一个序列它的第一个语句是入口语句
第二,由一个转移语句转到的语句是一个入口语句
比如说
由12转到的第3行这个语句
它是一个入口语句
第三,紧跟在转移与后边的语句是一个入口语句
也就是12之后
如果还有13这行语句的话
那么13也是一个入口语句
每个入口语句到下一个入口语句之间的语句序列
构成一个基本块
那么从3开始到12构成了一个基本块
我们接下来
可以将这段三地址代码
划分为两个基本块
1和2这两条语句就作为B1基本块
剩下的语句
作为循环所对应的另一个基本块B2
有了基本块的概念之后
我们就可以对基本块来进行优化
我们来看一下
如何来对它进行优化呢?
首先我们先学习一下
引用和定值的概念
假设有一个三地址语句 x=y+z
我们说这样的一条语句
通过对y和z的引用对x进行了定值
也就是y和z来确定x的值
一个名字的值
在基本块的某一点之后
如果还需要引用的话
我们就说
这个名字或者变量在这一点是活跃的
也就是说
如果x=y+z在这一点之后
我们还需要对X来进行使用的话
我们就说x在这一点是活跃的
然后我们来学习一下
基本块等价的概念
两个基本块的出口点
有同样的活跃的变量的集合
我们就说这两个基本块是等价的
对于其中的每个变量
定义其值的两个表达式
还需要相等
有很多等价的变换
可以用于基本块
包括局部变换或者全局变换
接下来我们讨论一下基本块的优化
基本块的优化
有如下的几个方法
首先我们可以删除
局部公共子表达式
比如说对一个语句的序列
a=b+c
b=a-d
c=b+c
d=a-d
我们观察到
b和d都是a减d
并且在d和b中间的语句
没有对a和d的操作
所以我们就可以来压缩它
把它变为d=b
第二我们可以删除死代码
比如说
有一个定值 x=y+z
在这之后,并没有对x来进行引用
我们就把X称为死变量
也就是说
其实不需要在这条语句对x来进行计算
第三
我们可以通过交换相邻的独立语句
来对基本块进行优化
比如说
t1=b+c
t2=x+y
假设t1和t2不相同
x和y都不是t1
并且b和c都不是t2
那么我们就可以交换
这些相邻的独立语句
将它变化为t2=x+y
t1=b+c
然后,再进行后继的其他优化
最后,
我们可以考虑一些基本的代数变换
比如说
我们计算得到x=x+0
x=x×1
这样的语句
我们都可以把它删掉
如果是x=y**2
我们可以将它改为x=y×y
流图是我们把控制流的信息
加到基本块的集合
形成一个有向图
来表示我们程序的工作顺序
我们看到我们从B1开始
有一个向下的箭头进入到B2
从B2出发
继续可以向下
当然B2本身作为一个循环
从B2的输出边有一个指回B2开头的
这样的一条边
流图当中包括首结点
也就是整个程序最开始的结点
那么对于我们这个图来说
B1就是首结点
同时包括前驱和后驱的概念
那么B1就是B2的前驱
B2就是B1的后继
什么是循环呢?
我们说对一个循环的内部
所有的结点是强连通的
并且这个循环只有一个唯一的入口
我们看到对于B2来说就是一个循环
对于B2来说
所有内部的结点是强连通的
并且只有一个唯一的入口
当然我们知道在程序中
可能出现双重循环
甚至三重循环
甚至更多的循环
所以这个循环
就包括内循环和外循环
下一个概念是下次引用信息
对于基本块
我们如果从最后一个语句块
反向扫描到第一个句子块
我们就可以得到下次引用信息
比如说
对一个三地址语句x=y op z
我们使用y和z来决定x的值
那么假设这个语句序列是这样
第i条当中x=y op z
然后中间没有对x的赋值
第j行语句当中引用了X
然后没有对x的赋值
在第k行语句当中引用了x
那么我们可以通过反向去扫描
我们知道第i行语句当中
是对x进行定值
在第k行语句当中
是最后一次引用了x
利用下次引用信息
我们可以来压缩临时变量
需要的空间
这一小节就到这
谢谢大家
-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