一个编程语言的设计笔记( 一 )

    科技2022-07-11  94

    前言

    本文需要一丢丢的基础才能看懂本文是乱扯

     

    设计目的

    作为一个高效、实用的中间语言/表示(IR/IL)以用于多前端多目标的编译、和代码转换等目的

     

    项目介绍

    本设计服务于Ordinary.Ir项目,Ordinary.Ir项目是Ordinary项目的一个子项目,这个项目在本文发布时正在使用AGPL协议开源

     

    长期计划

    前端

    msilllvmc++……

    后端

    spirvmsilllvmglslopencl-cptx……

     

    目前计划

    设计出大体框架,定义各个模块及大略给出他们的相关信息

     

    设计( 一 ):生成大体概念

    IR

    使用节点结构表示,以易于分析和更改,就像这样:

    [ 指令1 ] -> [ 指令2 ] -> [ 指令3 ] ->……

    就这样,大量的IR节点组成IR网络

     

    IR指令

    IR指令有四种接口:

    入口出口值输出值输入

    每种接口可有存在多个

    根据指令的不同,其各类接口和接口的数目、意义等也会不同

     

    指令的入口、出口

    一个指令的出口接口可以连接另一个指令的入口接口,出口和入口的连接组成了整个IR网络的大体架构

     

    出口可以连接多个入口,这种情况代表程序运行出这个出口后“并行”执行进入这些个入口

    入口也可以有多个出口与之连接,被多连接的入口的执行需要与之连接的出口全部执行完成作为前提条件

    这样设计的目的是把程序的流程更加无死角地呈现给程序员和优化器以及编译器

     

    值的输入、输出

    值的输出只能输出一个值。值是都是常量,不能被更改的,它只能被输出

    但是值的输入可以输入多个值,前提是这输入的多个值所属的指令中必有且仅有一个指令一定会被执行

    熟悉中间语言的朋友们就会发现了,这不就是phi节点吗

     

    函数

    分治法是解决问题的重要途经,用户可以自定义指令,自定义指令由一系列指令连接组成

     

    IR构建器

    图结构是为了把更清晰地把IR呈现给用户、优化器、编译器等需要读取IR的机构,这并不意味着它容易写入

    直接让用户手动编码IR,用户看见一大坨的网络和节点,添加一条指令都不知道该往哪个节点上加

    故一个IR构建器还是被需要的

     

    IR的高等化

    元编程总能让人兴奋,给IR添加静态元编程的功能也是件令人心潮澎湃的事。

     

    刨析现有的一些静态元编程:

    C++ 宏C++ 模板rust 宏

    发现:编译器进行元处理时的一个共有的前提条件是“识别到到元编程的内容”

    所以就可以把这个作为切入点

     

    LLVM-IR编译器

    llvmir编译器是首要要实现的编译器之一,llvm项目有许多的编译器,可以把llvm-ir编译成各种操作系统和cpu上的程序,只要能编译成llvm的ir,那么编译器的大部分需求都差不多算是解决了

     

    LLVM-IR没有这样的并行

    此问题可以通过简单地把并行的指令串接在一起解决,或者从线程池里抽取线程

     

    自定义指令无法直接转换成LLVM的函数

    这样的情况很复杂,多入口,多出口,多线程,,,

    多入口还可以生成多个函数,多出口什么鬼,,,

    goto、switch、或者传入函数指针,

     

    而线程的等待同样需要一个线程系统来提供线程池之类的东西,而这个系统需要单独生成一套ir,这样就说明多入口多出口的功能是一种扩展功能,如果是这样的话那这个ir就未免过于高级了。故一个较为底层的ir设计还是有必要的。可以把多出口的多线程支持作为IR一项“标准库的语言集成”

     

    设计( 二 ):略入部分细节

    异步

    上面说到,把多出口多入口什么的作为一项“标准库的语言集成”未免有些死板,丧失了可扩展性。那么把他当作是一项扩展就成了一种可能性。

    可是既然出口入口都成了扩展,那么原来的ir结构又要怎么表示呢?

    一个解决方案:对于可以直接展开成序列的IR异步就直接展开,展不开的用线程池,其中线程池的部分需要扩展

     

    可任意扩展的IR

    对ir的操作抽象成命令,扩展通过记录命令,记录下扩展指令的对象,后期处理时通过记录表迅速定位需要处理的地点

    如果想要像

     

    增量修改

    Ir的处理免不了需要很多次处理,如果每次处理都直接修改原来的,那么下次编译就要再生成一遍,如果修改创建一个副本或一个新的IR体系,也免不了再生成,于是增量更改是一个不错解决方案,每次修改都附在在原来的上面,既保留了原来的,又生成了新的

    上面的异步,就可以设定一个处理程序,把不适配llvm的部分增量处理,既让未处理的IR得到保留,又可以访问到处理后的代码

     

    元数据

    给ir对象附加上一些额外的数据有很多用途。

    比如switch,我们可以把一些更有记录命中的case贴上标签,告诉编译器把这些case往前面摆以提高运行速度

    或者是给某些性能关键区的函数调用贴上标签,告诉编译器内联这些函数来提高性能

     

    如果可以的话,还可以让ide在编码时期就去自动分析case的命中率什么的,然后自动附上元数据

     

    静态元编程

    为了防止用户搞各种xml和各种奇葩自创语言生成代码,编译期元编程很有必要

    宏和模板什么的未免都有些死板,不如直接让用户用ir写ir构造器,ir可以访问ir网络,并更改网络

     

    分析数据的存储

    编译器处理ir会对其各种分析,分析常量性的传播来决定哪些东西可以编译期计算,分析哪些东西是冗余可以被清理的,这些信息无一例外都会附在ir对象上

     

    那这ir对象一个得多肥啊,那么大肚量,既要被附上增量修改信息,又要被附上元数据、还要被附上一大堆分析结果,可能还要被附上ide的信息

    解决方案:除了每个对象都弄一个字典外,还可以:

    每一类信息注册成一个数,0,1,2,3,4,统一给每个对象都弄个数组,我要A类型的附加数据,就去查表,发现A对应的数是3,那么每个对象中A类型的数据就在对象的那个数组的第三个成员里

     

    设计( 三 ):了解内部机理

    哲学

    创造一个可以作为地基,让其他玩家在上面自由发挥的体系,首先要明确:没有任何东西能表示绝对的抽象,抱有“存在一个最优解”的想法是不科学的。

    作为ir的设计者,能做的只是尽力让ir适应它的用途

    提供一个足够“好用”的ir,接近好用这个目标需要ir足够底层,以来表示尽可能多的东西,这才是“底层”应该服务的地方,如果盲目追求某个性质而忽略了它的本来目的就会造成损失,牺牲某种性质换取实用性是允许的

     

    最低成本自举

    此时我们的ir已经上升为一门正正统统的编程语言了

    一说到自举,我们想到的肯定就是用c之类的语言写第一个编译器,然后再用自己的语言重写一遍这个编译器

    实际上没这么麻烦,只要写一个“打火石”就够了

    “打火石”就是一个效率能有多低就有多低的解释器,反正火烧起来了打火石就扔了,也就用一次

    先用ir写好ir的编译器

    然后用“打火石”运行这个编译器来编译编译器自己

     

    IDE

    用ir实现ir的第一个编译器需要一个ide的扶持,这个ide需要能够生成编译器可以输入的ir格式以用于解释执行

    一般是序列化后的形式

     

    原始API

    静态元编程毕竟要在ir里调用编译器里操作ir的指令,这就意味着编译器要向ir开放api,就像那些加减乘除什么的一样

     

    有组织地生成代码

    组织元编程也是需要框架的

    你看c++的那个vector<int>,难道每次编译都要重新拼凑出一个vector<int>吗,我能不能把第一次生成的vector<int>的数据缓存呢,即便只是语法树

    这需要一个元编程的框架,自动决定什么时候要重新生成,而且他要在编码期运行,而不是编译期。

    你写着写着代码,缓存就构建好了,然后当你按下f5的时候,那就是易语言级的启动速度

    这说明ir编译器要提供一套编码期api。

     

    Processed: 0.029, SQL: 8