依星源码资源网,依星资源网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

【好消息,好消息,好消息】VIP会员可以发表文章赚积分啦 !
查看: 44|回复: 0

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

[复制链接] 主动推送

1万

主题

1万

帖子

1万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
12008
发表于 2024-11-10 12:48:16 | 显示全部楼层 |阅读模式
用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
一 绪论
芯片是一个硬件,接收的是二进制的指令,要想让自己的编程语言编程指令,就需要一个编译器。
这个部分的重要程度丝毫不亚于芯片本身。最近国内很多公司在做AI芯片,经常出现芯片很快就做出来了,但芯片受限于编译器无法发挥最大能效的窘境。总之,了解编译器还是很重要的。
这个系列讲讲如何用LLVM做一个最简单的编译器。万变不离其宗,其他复杂的编译器可以从这个例子上拓展。
本部分主要讲基础知识,不需要了解细节,但是对编译器整体如何工作的要有概念。
不专业做编译器,难免有错误,欢迎指出,另外,部分图来自网络。

二 LLVM是个什么东西
首先一个东西要搞明白,为什么要用LLVM? LLVM的是什么?
LLVM提供了一个模块化的编译器框架,让程序员可以绕开繁琐的编译原理,快速实现一个可以运行的编译器。
常见的结构如下图。

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
主要由三个部分组成。
前端:将高级语言例如C或者其他语言转换成LLVM定义的中间表达方式 LLVM IR。例如非常有名的clang, 就是一个转换C/C++的前端。
中端:中端主要是对LLVM IR本身进行一下优化,输入是LLVM, 输出还是LLVM, 主要是消除无用代码等工作,一般来讲这个部分是不需要动的,可以不管他。
后端:后端输入是LLVM IR, 输出是我们的机器码。我们通常说的编译器应该主要是指这个部分。大部分优化都从这个地方实现。
至此,LLVM架构的模块化应该说的比较清楚了。很大的一个特点是隔离了前后端。
如果你想支持一个新语言,就重新实现一个前端,例如华为“仓颉”就有自己的前端来替换clang。
如果你想支持一个新硬件,那你就重行实现一个后端,让它可以正确的把LLVM IR映射到自己的芯片。
接下来我们大致讲讲前后端的流程。
二 前端在干什么
我们以Clang举例,前端主要实现四件事。

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
经过词法分析、语法分析、语义分析、LLVM IR生产,最终将C++转化成后端认可的LLVM IR。
词法分析:将编程语言取出一个个词,遇到不认识的字符就报错。例如将a=b+c 拆成a,= ,b ,+, c
语法分析:将语法提取出来,例如你写了个a+b=c, 明显不符合语法,直接报错
语义分析:分析一下你写的代码实际含义是不是对,例如a=b+c, a,b,c有没有定义,类型是不是对的
LLVM IR生产:经过上述三步,将你写的代码转化成树状描述(抽象语法树),然后再转化成IR定义的IR即可。
举个直观的栗子,你写的C++
// add.cpp
int add(int a, int b) {
return a + b;
}
生产的LLVM IR
(这个地方你不需要看懂每个细节,知道大概想类汇编的语言就行了, 专业的形式叫SSA, Static Single Assignment (SSA)
; ModuleID = 'add.cpp'
source_filename = "add.cpp"
target datalayout = "e-m-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.15.0"


; Function Attrs: noinline nounwind optnone ssp uwtable
define i32 @_Z3addii(i32, i32) #0 {
%3 = alloca i32, align 4
%4 = alloca i32, align 4
store i32 %0, i32* %3, align 4
store i32 %1, i32* %4, align 4
%5 = load i32, i32* %3, align 4
%6 = load i32, i32* %4, align 4
%7 = add nsw i32 %5, %6
ret i32 %7
}
三 后端在干什么
后端把你的LLVM转换成真正的汇编(或者机器码)。主要的流程如下。这个我们要重点讲讲,因为后续我们就是要实现一个这个东西支持一个新的芯片。

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
按步骤一个一个讲。
3.1 DAG Lowering
这个主要负责将你的LLVM IR转换为有向无环图,便于后续利用图算法优化。
例如将下面的LLVM IR 转换成图,每个节点是一个指令。

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
3.2 DAG Legalization
DAG图合法化,3.1中的DAG图都是LLVM IR指令,但实际上LLVM IR指令不可能被芯片全部支持,这个步骤就是替换这些不合法的指令。
3.3 Instruction Selection
这个步骤其实和3.2算是一起的功能,都是为了将LLVM IR转换成机器支持的Machine DAG.

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
如上图,将store换成机器仍可的st, 将16位的寄存器转向32位。一切向机器指令靠拢。
3.4 Scheduling
这个步骤主要是调整指令顺序的,从有向无环图再展开成顺序的指令。
例如把下面的指令调成这样的。

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

把%C的store提前一些,因为下一条ld要用C啦。
3.4 SSA-based Machine Code Optimization
这一步骤主要是做一些公共表达式合并啊去除的操作。
3.5 Register Allocation
这一步就要分配寄存器了。在3.5之前我们认为寄存器其实是可以无限用的,但实际硬件的寄存器有限的。所以我们得考虑寄存器数量与寄存器值的生命周期,将虚拟的寄存器替换成实际的寄存器。这个一般会用到图着色等等算法,贼复杂,好在LLVM都实现好了,不用在重复造轮子。
例如一个芯片,有32个可用的寄存器,如果函数使用到了64个,多的就只能压如堆栈或者等着了。
具体怎么分配的,知乎有专家研究,见下面的文章。Frank Wang:LLVM寄存器分配(一)
3.6 Prologue/Epilogue Code Insertion
这个主要是加上函数调用前的指令和函数结束后的指令。主要是调用前把参数存下来,调用后把结果写到固定的寄存器里。
3.7 Peephole optimizations
这个步骤主要是对代码再最后抢救一番。比如把x*2换成x<1
再比如下面这样

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念

用LLVM写一个芯片编译器(一)——一文读懂编译器基本概念
将两个32bit的存储换成一个64bit的存储
3.8 Code Emission
最后一步显然,将上述优化好的中间格式转换成我们真正需要的汇编,由汇编器翻译成机器码,大功告成。
三 总结
这篇文章,我们介绍了程序编译的最基本概念,编译中的大部分流程都有所涉及。下一章开始我们介绍如何用LLVM快捷的实现上面的流程。LLVM的精髓就在于,你不必对上面每一个步骤内部如何实现的彻底了解细节。你只需要知道有这么个东西就能很快攒出你的编译器。

相关帖子

扫码关注微信公众号,及时获取最新资源信息!下载附件优惠VIP会员5折;永久VIP免费
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

免责声明:
1、本站提供的所有资源仅供参考学习使用,版权归原著所有,禁止下载本站资源参与商业和非法行为,请在24小时之内自行删除!
2、本站所有内容均由互联网收集整理、网友上传,并且以计算机技术研究交流为目的,仅供大家参考、学习,请勿任何商业目的与商业用途。
3、若您需要商业运营或用于其他商业活动,请您购买正版授权并合法使用。
4、论坛的所有内容都不保证其准确性,完整性,有效性,由于源码具有复制性,一经售出,概不退换。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
5、用户使用本网站必须遵守适用的法律法规,对于用户违法使用本站非法运营而引起的一切责任,由用户自行承担
6、本站所有资源来自互联网转载,版权归原著所有,用户访问和使用本站的条件是必须接受本站“免责声明”,如果不遵守,请勿访问或使用本网站
7、本站使用者因为违反本声明的规定而触犯中华人民共和国法律的,一切后果自己负责,本站不承担任何责任。
8、凡以任何方式登陆本网站或直接、间接使用本网站资料者,视为自愿接受本网站声明的约束。
9、本站以《2013 中华人民共和国计算机软件保护条例》第二章 “软件著作权” 第十七条为原则:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。若有学员需要商用本站资源,请务必联系版权方购买正版授权!
10、本网站如无意中侵犯了某个企业或个人的知识产权,请来信【站长信箱312337667@qq.com】告之,本站将立即删除。
郑重声明:
本站所有资源仅供用户本地电脑学习源代码的内含设计思想和原理,禁止任何其他用途!
本站所有资源、教程来自互联网转载,仅供学习交流,不得商业运营资源,不确保资源完整性,图片和资源仅供参考,不提供任何技术服务。
本站资源仅供本地编辑研究学习参考,禁止未经资源商正版授权参与任何商业行为,违法行为!如需商业请购买各资源商正版授权
本站仅收集资源,提供用户自学研究使用,本站不存在私自接受协助用户架设游戏或资源,非法运营资源行为。
 
在线客服
点击这里给我发消息 点击这里给我发消息 点击这里给我发消息
售前咨询热线
312337667

微信扫一扫,私享最新原创实用干货

QQ|免责声明|小黑屋|依星资源网 ( 鲁ICP备2021043233号-3 )|网站地图

GMT+8, 2024-11-23 22:38

Powered by Net188.com X3.4

邮箱:312337667@qq.com 客服QQ:312337667(工作时间:9:00~21:00)

快速回复 返回顶部 返回列表