当前课程知识点:编译技术 >  第七章 代码生成 >  7.3 基本块和流图 >  7.3 基本块和流图

返回《编译技术》慕课在线视频课程列表

7.3 基本块和流图在线视频

下一节:7.4 一个简单的代码生成器

返回《编译技术》慕课在线视频列表

7.3 基本块和流图课程教案、知识点、字幕

各位同学大家好

这节课我们继续来学习代码生成

我们来讨论基本块和流图

首先我们需要想一下

怎样为三地址序列

生成对应的目标代码

我们来看一个例子

针对这样的一段代码来说

里边包含着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 编译技术绪论

--1.1 编译技术绪论

--编译原理介绍--作业

第二章 词法分析

-2.1  词法记号 串和语言

--2.1 词法记号 串和语言

--2.1  词法记号 串和语言--作业

-2.2  正规式 状态转换图

--2.2 正规式 状态转换图

--2.2  正规式 状态转换图--作业

-2.3  有限自动机

--2.3 有限自动机

--2.3  有限自动机--作业

-2.4  DFA构建 子集构造法 DAF化简

--2.4 DFA构建

-2.5 Lex

--2.5 词法分析工具Lex

第三章 语法分析

-3.1 上下文无关文法

--3.1.1 语法分析概述

--3.1.2 上下文无关文法定义

--3.1.3 推导

--3.1.4 二义性

-3.2 自上而分析中的文法

--3.2.1 消除左递归

--3.2.2 提取左因子

--3.2 上下文无关文法--作业

--3.2.3 语言和文法

--3.2.3 语言和文法--作业

-3.3 自上而下分析

--3.3.1 first follow

--3.3.2 LL(1)文法

--3.3.3 递归下降分析

--3.3.4 非递归下降分析的预测分析器

-3.4 自下而上分析

--3.4.1 归约句柄

--3.4.2 移进归约分析过程

--3.4 自下而上分析--作业

-3.5 LR分析器

--3.5.1 LR分析器

--3.5.2 活前缀

--3.5.3 SLR分析方法

--3.5.4 规范的LR分析方法

--3.5.5 LALR分析方法

--3.5.6 LR分析方法特点

--3.5.7 非二义且非LR的上下文无关文法

第四章 语法指导的翻译

-4.1 语法制导的定义

--4.1.1 属性文法

--4.1.2 属性依赖图和计算次序

--4.1 语法制导的定义--作业

-4.2 S属性的自下而上计算

--4.2.1 S属性的自下而上计算

--4.2.2 栈代码

-4.3 L属性定义

--4.3.1 L属性定义

--4.3.2 翻译方案

--4.3.3 预测翻译器的设计

--4.3 L属性定义--作业

-4.4 L属性的自下而上计算

--4.4.1 L属性的自下而上计算

--4.4.2 模拟继承属性的计算

--4.4 L属性的自下而上计算--作业

第五章 运行时存储空间的组织与管理

-5.1  概述

--5.1 概述

--概述-作业

-5.2  全局栈式存储分配

--5.2 全局栈式存储

-5.3  调用序列

--5.3 调用序列

-5.4 非局部名字的访问

--5.4 非局部名字

--5.4 非局部名字的访问--作业

第六章 中间代码生成

-6.1 中间代码生成

--6.1 中间代码生成概述

-6.2 作用域信息的保存

--6.2 声明语句-作用域信息的保存

第七章 代码生成

-7.1 代码生成器设计中的问题

--7.1 代码生成器的设计中的问题

-7.2 目标机器

--7.2 目标机器

--7.2  目标机器--作业

-7.3 基本块和流图

--7.3 基本块和流图

-7.4 一个简单的代码生成器

--7.4 一个简单的代码生成器

第八章 基于Python的编译器框架实现

-8.1 基于Python的编译器框架演示视频和代码

--8.1 基于Python的编译器框架演示

-8.2 代码介绍

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

7.3 基本块和流图笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。