您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

编译原理:抽象语法树是怎么变成机器码的

时间:2022-12-26 15:29:36  来源:今日头条  作者:底层技术栈

编译器在经过词法分析、语法分析之后,就把源代码变成了抽象语法树(AST)

接下来,编译器的任务就是把AST变成机器码

AST,是一个表示代码逻辑的树形结构,它是不能直接顺序遍历的,而只能递归遍历

递归遍历的逻辑更复杂,不适合用在机器码、汇编码、字节码上。

越是底层代码越贴近数字电路,而数字电路不适合直接处理复杂的逻辑。

递归也属于复杂的逻辑,

所以C语言的入门程序之一就是“汉诺塔”,而数学归纳法可以成为一种常用的证明方法。

AST的树形结构,肯定是不适合直接在CPU上运行的,而要先把它变成机器码。

AST是怎么变成机器码的?

1,语义分析,

语义分析的作用有3个:

1)类型检查,

2)常量表达式的计算,

3)函数重载,

如果不是OOP语言,语义分析时不需要考虑函数重载问题。

语义分析最主要的作用还是类型检查

编译器报出来的很多错误或警告信息,都是类型检查时给出来的,例如:

A* p = malloc(sizeof(A));

C++中就会报错:从void指针到A的指针没有加类型转换(type cast)。

AST

赋值运算符=两边的类型,是语义分析时首先要检查的(其他运算符也一样)。

如果类型不匹配,在强类型语言的编译器里就要给出错误提示

另外,sizeof(A) 都是常量表达式,也要在语义分析时计算出来。

把常量表达式提前在编译时计算出来,可以提高运行时的速度。

如果是脚本语言解释器的话,在语义分析之后,就可以直接在AST运行了:

给每个运算符节点定义一个处理函数,该调用哪个就调用哪个,就可以得出程序的结果;

if / while / for 等分支循环的关键字,也可以一样看做是运算符。

如果是编译器虚拟机,还需要继续往下处理。

虚拟机也是运行机器码的,只是和CPU的机器码不一样:虚拟机的机器码一般叫字节码

2,三地址码的生成,

三地址码,是编译器的后端常用的中间代码。

生成了三地址码之后,就把AST的树形结构变成了顺序结构了,跟汇编码、机器码、字节码一样了。

struct A { int x, y; };

A* p = malloc(sizeof(A));

生成的三地址码是这样的:

call ret; malloc, 8

assign p; ret

第一个词是三地址码的指令(opcode),分号前面的是目的操作数(dst operand),分号后面的是源操作数列表(src operands list),多个源操作数之间以逗号分隔。

按照源代码的执行顺序,把AST遍历一遍,就可以生成三地址码

源代码里分为顺序语句、if else语句、while语句、for语句等等,每种语句类型生成的三地址码是不一样的。

if else语句的三地址码会有分支跳转:往函数的结尾方向跳转。

while语句、for语句的三地址码会有循环跳转:往函数的开头方向跳转。

for (i = 0; i < 10; i++) printf("%dn", i);

上述for循环的AST和三地址码

从图中可以看出来,三地址码跟汇编码的差异非常小!

汇编码,是机器码人类阅读版[呲牙]

生成了三地址码之后,把它变成机器码还是很容易的(如果不考虑运行效率的话)。

编译器后端的各种优化,主要还是为了让生成的机器码运行更快,而不仅仅是为了让机器码运行正确

编译器的后端优化是个无底洞,因为程序员对代码的理解总是比编译器更深刻。

毕竟程序员是个大活人,而编译器有赖于程序员给它升级版本。

3,正确运行相关的优化,

加载(load)和保存(save)指令的位置,都是跟机器码的正确运行相关的优化。

除非每条运算指令都把结果写到内存,否则加载和保存指令的位置必须正确。

加载指令的位置在基本块开头保存指令的位置在基本块的末尾

基本块,指的是没有跳转指令的顺序语句块

for (i = 0; i < 10; i++) printf("%dn", i);

还是以前面的for循环为例子:

assign i, 0

这就是第1个基本块,因为接下来就要比较 i < 10了,而且还可能从后面跳回来多次比较。

cmp i, 10

这是第2个基本块,接下来会根据i < 10的比较结果进行跳转。

call printf, "%dn", i

inc i

这两行是第3个基本块,它们之间也没有跳转,而再往后就要跳转回开头,再次检查条件表达式。

跳转的源位置和跳转的目的位置,都是一个新的基本块的开始位置:

因为它们(前面或后面)的代码的执行分支可能变化的,所以要单独划到一个基本块里。

for循环的流程图

如果在某个基本块里修改了某个变量,就要在末尾把它保存到内存

如果在某个基本块里要使用某个变量,就要在开头把它加载到寄存器

如上图:

对 i 赋值 0 之后要把它保存到内存,见绿色的save i指令;

在比较i < 10之前要把它从内存加载到寄存器,见绿色的load i指令。

这样生成指令,就可以保证运行结果的正确。

但为了让它运行的更快,一般会把循环内的加载放到循环的开头,把循环内的保存放到循环的末尾

当然,这么做的前提是:循环的出口入口必须都是唯一的

goto不受待见,从编译器的层面来看,就是goto会导致循环的出口入口有多个。

4,变量之间的冲突,

互相冲突的变量不能使用相同的寄存器,这是寄存器分配的原则。

怎么判断变量之间互相冲突呢?

就是某个变量如果在后面还要用,那么它跟其他变量就是冲突的。

例如:

a = 1;

b = 2;

c = a + b;

那么a和b就是冲突的。

因为第3行代码都要用到它们两个,所以在第2行代码的时候:a占用的寄存器不能腾出来,b必须找其他寄存器用。

第3行代码之后,a和b都没用了,c可以跟a或b的任何一个使用相同的寄存器。

所以上面的代码翻译成汇编,可以这样:

mov eax, 1

mov ebx, 2

add eax, ebx

a和c都使用eax,b使用ebx。

但是a和b不能都使用eax,否则结果就是错的。

变量之间是否冲突,要从后往前看。

编译器里在检查变量的冲突时,都是从函数的末尾往开头反向遍历每一条代码,看看哪些变量之间是冲突的。

有兴趣的可以看看我写的scf编译器框架的代码,在文件scf_basic_block.c里。

5,寄存器的分配,

确定了变量之间的冲突情况之后,就可以给代码里的变量分配寄存器了。

例如:

a = 2;

b = 3;

c = 4;

d = a + b + c;

这个例子的abc三者之间都是冲突的,因为在第4行同时用到了它们3个。

画个变量的冲突图如下:

变量的冲突图

a, b, c之间是互相冲突的,每一对冲突的变量之间有一条连线,所以正好画成一个三角形。

在分配寄存器时,abc互相之间不能分配相同的寄存器。

也就是说,把寄存器的编号作为颜色的话,上图三角形的3个顶点不能着同样的颜色。

变量的冲突图上,每一条边的两个端点必须着不同的颜色

这就是用于寄存器分配的图的着色算法。

分配完寄存器之后就好办了,按照每种CPU的手册生成指令的机器码就可以了。

例如:

给a, b, c分别分配eax, ebx, ecd,

d与a共用eax,

那么汇编指令就是:

mov eax, 2

mov ebx, 3

mov ecx, 4

add eax, ebx

add eax ecx.

x64的机器码我实在记不住,但在汇编层面,我还是可以充当个人形编译器的[大笑]

有兴趣的可以看看我的scf编译器框架的源码,非常的清晰。

编译原理(龙书)确实没怎么细说后端是怎么写的,只是提了一下图的着色算法。

不过对于我来说,我只要知道有这么个软件,我就能把它写出来

求个赞赏[捂脸]

虽然重阳一生不弱于人,但还是要靠九阴真经来破解古墓派的武功啊。



Tags:编译   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
C++中的外部模板及其在当前编译文件中的实例化
在C++中,模板是一种泛型编程的工具,它允许程序员以一种类型无关的方式编写代码。然而,模板的一个常见问题是它们会导致编译时间增加,特别是在大型项目中,当多个源文件包含相同的...【详细内容】
2024-04-11  Search: 编译  点击:(3)  评论:(0)  加入收藏
解除Java反复编译的困扰方法,优化开发效率
在Java开发过程中,反复编译是一个常见的问题,特别是在大型项目或者需要频繁修改代码的情况下。每次修改代码后都需要重新编译整个项目,这样耗费了大量的时间和资源,降低了开发效...【详细内容】
2023-12-19  Search: 编译  点击:(151)  评论:(0)  加入收藏
C++模板背后的黑箱操作:编译器
一、编译器如何处理模板1.模板代码的处理为了理解模板的复杂性,你需要了解编译器是如何处理模板代码的。当编译器遇到模板方法定义时,它会进行语法检查,但实际上不会编译模板。...【详细内容】
2023-12-08  Search: 编译  点击:(220)  评论:(0)  加入收藏
微信小程序的编译原理
2021年来,随着科技的进步,人们的生活水平也在不断提高。现在,微信小程序已经成为了现代人生活中不可或缺的一部分,它可以帮助我们更方便地查找信息,购物,预订机票和酒店,进行社交等...【详细内容】
2023-12-06  Search: 编译  点击:(128)  评论:(0)  加入收藏
解密 Python 如何调用 Rust 编译生成的动态链接库
楔子Rust 让 Python 更加伟大,随着 Rust 的流行,反而让 Python 的生产力提高了不少。因为有越来越多的 Python 工具,都选择了 Rust 进行开发,并且性能也优于同类型的其它工具。...【详细内容】
2023-11-29  Search: 编译  点击:(191)  评论:(0)  加入收藏
C++编译优化:如何优化编译器的输出代码质量
在当今的软件开发世界中,C++以其高效的性能和广泛的应用领域而受到开发者的青睐。然而,随着项目规模的不断扩大和性能需求的日益增长,如何优化编译器的输出代码质量成为了亟待...【详细内容】
2023-11-16  Search: 编译  点击:(221)  评论:(0)  加入收藏
编译器的并行化与多线程优化
在计算机科学领域,编译器是将高级语言代码转换成机器语言的重要工具。编译器的性能对于程序的执行效率具有重要影响。为了提高编译器的性能,研究人员一直致力于并行化和多线程...【详细内容】
2023-11-16  Search: 编译  点击:(202)  评论:(0)  加入收藏
C 语言编译器(IDE)初学者指南:选择适合你的工具
一、前言在当今的软件开发世界中,C语言仍然是一种非常重要的编程语言,被广泛用于系统编程,游戏开发,嵌入式系统等领域。对于C语言的初学者来说,选择一款合适的编译器(IDE)是他们学...【详细内容】
2023-11-14  Search: 编译  点击:(239)  评论:(0)  加入收藏
编译器前端与后端:理解编译过程中的不同阶段
编译器是将高级程序语言转换为机器语言的重要工具。在编译过程中,编译器可以被划分为前端和后端两个主要部分。前端负责处理源代码的词法分析和语法分析,而后端则负责代码优化...【详细内容】
2023-11-14  Search: 编译  点击:(217)  评论:(0)  加入收藏
Python 既是解释型语言,也是编译型语言
不知道有没有小伙伴跟我一样,刚开始学习 Python 的时候都听说过 Python 是一种解释型语言,因为它在运行的时候会逐行解释并执行,而 C++ 这种是编译型语言图片不过我今天看到了...【详细内容】
2023-11-08  Search: 编译  点击:(288)  评论:(0)  加入收藏
▌简易百科推荐
Netflix 是如何管理 2.38 亿会员的
作者 | Surabhi Diwan译者 | 明知山策划 | TinaNetflix 高级软件工程师 Surabhi Diwan 在 2023 年旧金山 QCon 大会上发表了题为管理 Netflix 的 2.38 亿会员 的演讲。她在...【详细内容】
2024-04-08    InfoQ  Tags:Netflix   点击:(2)  评论:(0)  加入收藏
即将过时的 5 种软件开发技能!
作者 | Eran Yahav编译 | 言征出品 | 51CTO技术栈(微信号:blog51cto) 时至今日,AI编码工具已经进化到足够强大了吗?这未必好回答,但从2023 年 Stack Overflow 上的调查数据来看,44%...【详细内容】
2024-04-03    51CTO  Tags:软件开发   点击:(7)  评论:(0)  加入收藏
跳转链接代码怎么写?
在网页开发中,跳转链接是一项常见的功能。然而,对于非技术人员来说,编写跳转链接代码可能会显得有些困难。不用担心!我们可以借助外链平台来简化操作,即使没有编程经验,也能轻松实...【详细内容】
2024-03-27  蓝色天纪    Tags:跳转链接   点击:(13)  评论:(0)  加入收藏
中台亡了,问题到底出在哪里?
曾几何时,中台一度被当做“变革灵药”,嫁接在“前台作战单元”和“后台资源部门”之间,实现企业各业务线的“打通”和全域业务能力集成,提高开发和服务效率。但在中台如火如荼之...【详细内容】
2024-03-27  dbaplus社群    Tags:中台   点击:(9)  评论:(0)  加入收藏
员工写了个比删库更可怕的Bug!
想必大家都听说过删库跑路吧,我之前一直把它当一个段子来看。可万万没想到,就在昨天,我们公司的某位员工,竟然写了一个比删库更可怕的 Bug!给大家分享一下(不是公开处刑),希望朋友们...【详细内容】
2024-03-26  dbaplus社群    Tags:Bug   点击:(5)  评论:(0)  加入收藏
我们一起聊聊什么是正向代理和反向代理
从字面意思上看,代理就是代替处理的意思,一个对象有能力代替另一个对象处理某一件事。代理,这个词在我们的日常生活中也不陌生,比如在购物、旅游等场景中,我们经常会委托别人代替...【详细内容】
2024-03-26  萤火架构  微信公众号  Tags:正向代理   点击:(11)  评论:(0)  加入收藏
看一遍就理解:IO模型详解
前言大家好,我是程序员田螺。今天我们一起来学习IO模型。在本文开始前呢,先问问大家几个问题哈~什么是IO呢?什么是阻塞非阻塞IO?什么是同步异步IO?什么是IO多路复用?select/epoll...【详细内容】
2024-03-26  捡田螺的小男孩  微信公众号  Tags:IO模型   点击:(9)  评论:(0)  加入收藏
为什么都说 HashMap 是线程不安全的?
做Java开发的人,应该都用过 HashMap 这种集合。今天就和大家来聊聊,为什么 HashMap 是线程不安全的。1.HashMap 数据结构简单来说,HashMap 基于哈希表实现。它使用键的哈希码来...【详细内容】
2024-03-22  Java技术指北  微信公众号  Tags:HashMap   点击:(11)  评论:(0)  加入收藏
如何从头开始编写LoRA代码,这有一份教程
选自 lightning.ai作者:Sebastian Raschka机器之心编译编辑:陈萍作者表示:在各种有效的 LLM 微调方法中,LoRA 仍然是他的首选。LoRA(Low-Rank Adaptation)作为一种用于微调 LLM(大...【详细内容】
2024-03-21  机器之心Pro    Tags:LoRA   点击:(12)  评论:(0)  加入收藏
这样搭建日志中心,传统的ELK就扔了吧!
最近客户有个新需求,就是想查看网站的访问情况。由于网站没有做google的统计和百度的统计,所以访问情况,只能通过日志查看,通过脚本的形式给客户导出也不太实际,给客户写个简单的...【详细内容】
2024-03-20  dbaplus社群    Tags:日志   点击:(4)  评论:(0)  加入收藏
站内最新
站内热门
站内头条