当前课程知识点:Compilers Techniques >  7 Code Generation >  7.3 Basic Blocks and Flow Graphs >  7.3 Basic Blocks and Flow Graphs

返回《Compilers Techniques》慕课在线视频课程列表

7.3 Basic Blocks and Flow Graphs在线视频

下一节:7.4 A Simple Code Generator

返回《Compilers Techniques》慕课在线视频列表

7.3 Basic Blocks and Flow Graphs课程教案、知识点、字幕

各位同学大家好

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

我们来讨论基本块和流图

首先我们需要想一下

怎样为三地址序列

生成对应的目标代码

我们来看一个例子

针对这样的一段代码来说

里边包含着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

利用下次引用信息

我们可以来压缩临时变量

需要的空间

这一小节就到这

谢谢大家

Compilers Techniques课程列表:

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-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.2 Regular form

-2.3  Finite automata

--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 Syntax Analysis

-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.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--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.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--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 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--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

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--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 Basic Blocks and Flow Graphs笔记与讨论

也许你还感兴趣的课程:

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