Skip to content

Latest commit

 

History

History
181 lines (148 loc) · 8.92 KB

OverView.md

File metadata and controls

181 lines (148 loc) · 8.92 KB

关于编译/中间表示的思考

by hhw

sysy/c 高级语言

程序的高级表示 High Level Representation

"高级" 是与最底层的计算机硬件计算实相比较而言的, 更高级 ~= 更抽象, 意味着可以从更抽象/更高级的角度来描述程序, 而不必考虑计算机底层的具体实现. 在较高级的计算机编程语言中, 程序被抽象为 过程 + 数据, 这些过程和数据都是用较高的抽象来描述的, 贴合人类的认识和逻辑, 确与简单机械的计算机硬件/电路实现极为不同.

我们基于自己对程序的认识, 根据高级语言的语法和语法对应的语义, 将自己脑海中的 "程序", "翻译" 成高级语言编写的程序, 我们一定期许 脑海中的程序 和 用高级语言编写出来的 程序 是等价的, 这种 "等价性" 是又我们自己对要执行的计算任务的理解和对编程语言语义的理解保证的, 即, 我们期望: 对于相同的输入, 高级语言编写出来的程序的执行结果 要与 脑海中的程序的执行结果 相同. 而这种所谓的 "等价翻译", 可以说就是 一次 思维 到 高级编程语言的 "编译".

抽象的看, 我们想要执行某个计算任务, 首先要做的就是要 准确地描述和表示这个计算任务. 我们首先想到的一定是 "自然语言", 其次是各种编程语言. 根据离人类思维/逻辑习惯的远近, 离实际计算机硬件实现的远近, 可以将这些语言 从高倒低依次排列为:

人类思维 - 自然语言 - 高级编程语言 - 若干层的中间表示 - 汇编语言 - 机器语言 - (逻辑电路 - 数字电路 - 模拟电路 - 电子器件 - 电子物理属性)

而每一层语言都可以对该计算任务进行 "描述", 但不同语言离人类思维的距离由近及远, 描述任务的 "困难程度" or "复杂程度" 也便由近及远. 上一层是对下一层的抽象, 下一层是对上一层的 "实现".

自上而下看, 将人类思维翻译成自然语言/高级编程语言, 将高级编程语言经过若干层中间表示, 翻译成汇编语言(编译), 再翻译成机器语言(汇编), 再由逻辑电路按照物理规则实现计算, 输出结果. 每一个上层语言表示到下层语言表示的 "等价翻译", 都可以视作 Compile. 反之, 自下而上地看, 从物理规则出发, 经过一层层的封装和抽象, 最终直到我们的思维.

人自然有人类的逻辑思维, 我们也拥有了对于电子物理知识和电路理论知识, 如何建立两者之间层层的 "中间表示" 呢? 也就是如何 定义中间语言. 这是通过自下而上实现的, 通过层层的封装和抽象, 我们建立起了一系列的 中间语言.

从计算机/计算机编程语言的发展也可以看出这一规律, 即先有最简单的物理器件(如晶体管或二极管), 然后组成较为复杂的与或非逻辑电路, 然后香农指出这种逻辑电路可以模拟布尔代数, 而此前布尔已经说明布尔代数可以描述逻辑推断过程, 可以描述计算, 可以判定命题, 然后冯诺一曼结合图灵机图灵可计算, 设计出了 冯诺已满 存储执行式的 计算机体系结构. 确定了计算在机器上的实现, 也即确定了机器语言(01 序列). 为了更方便地编写机器语言, 又提出使用助记符来表示机器语言, 也就是汇编语言. 用汇编语言仍然十分麻烦, 于是定义了更接近人类思维的高级语言. 正是这样逐层抽象, 构造了纷繁的计算机系统. 同时, 在建立新的抽象也意味着要实现抽象的逆, 也就是实现[实现翻译或编译]的程序.

首先, 从计算理论上讲, 我们已经假设图灵机可计算的问题, 就是人类思维可计算的问题.

根据某种 "描述语言" 或者说是 "表示机制" 来对这个计算任务进行 描述和表示.

程序 = 算法(计算过程) + 数据, 用什么来表示计算过程, 用什么来表示数据

语法 + 语义

  • function 函数
  • 量/有值的量 data
    • variable 变量
    • constant 常量
  • 值的类型
    • base data type: int/float
  • statement 语句
  • expression 表达式
    • assignment

定义一层抽象/一层中间表示, 就要定义这种表示的 "原语", 即该层的 各种概念 和 语法语义.

而一个程序的中间表示, 自然有 使用各种概念进行表示(一般体现为内存中的数据结构), 和 根据语法语义编写的 程序描述.

IR Intermediate Representation

广义上讲, 从人类思维到电子电路的每一层抽象都可以视作是中间语言.

此处的 IR 是高级语言的下一层级, 即: 高级语言 - IR - else

作为高级语言的更低一层的中间表示, IR 比高级表示(sysy) 更 lower, 并且由于可能存在多种多样的高级语言, 中间表示一般会追求"高级语言独立", 追求能够 "通用地"/Universial 表示程序语义.

Value, Type, Instruction, Module, Function

  • Value:
    • Virtual Base Class for 'Value'
    • 4 types of Value:
      • ValueRank: Constant, Global, Argument, Instruction
      • all 'Variable' is generated by Instruction
      • why use these four rank? let us consider the 'value' in our programm, what source can generate value?
        • obvirously constant is represented by Constant,
        • local variable can generate from alloca instruction, or from the operating of Values
        • global variable, global function use Global
        • Besides, function arguments is very Special, it is directly passed from the caller function. so we use we to represent.
    • Data Members:
      • mType
    • Methods
      • rank(), getType()
      • isXXX(): Value rank check
      • as<XXX>(): type cast
      • is<XXX>(): type check
      • dump(), dumpXXX(): virtual function for dump human readable text
  • Type:
    • Type System for IR, identify the type of the Value
    • TypeRank: Void, Integer, Float, Pointer, Array, Function
    • Data Members: None, use rank() method to identify the rank of the Type
    • Methods:
      • as(): type cast
      • dump(), dumpName()
      • getFixedSize(): fixed size of the type, determined by the class of the Type
      • getSize(DataLayout& ): actrual size of the Value with Type on Sepecific DataLayout
    • Derived Calss:
      • VoidType
      • IntegerType
      • FloatPointType
      • PointerType
      • FunctionType
      • ArrayType
  • ValueRef:
    • user/instruction -ref/use- value
    • DataMembers:
      • Value* value, Instruction* user
      • ValueRef* prev, next
    • Methods:
      • delete copy and move constructor/=, for what?
  • UserIterator
  • UserList
  • TrackableValue: public Value
    • Data:
      • UserList mUsers
  • ValueRefHandle
  • Instruction: public TrackableValue
    • Data:
      • mInstID, mOperands, mBlock, mLabel
      • InstructionID, Deque, BasicBlock*, string
      • Deque<ValueRefHandle> mOperands
        • front()/back()
        • push_front()/push_back()
        • pop_front()/pop_back()
    • Methods:
      • Value* getOperand(uint32_t idx)
      • ValueRef* addOperand(Value* val)
      • insertBefore()
      • clone()
    • Derivied Classes:
      • ...
  • ConstantRank
  • ConstantValue: public Value
    • Methods:
      • isEqual()
      • hash()
    • Derived:
      • ConstantInteger
        • mValue
      • ConstantFloatingPoint
        • mValue
  • GlobalValue: public TrackableValue
    • Data:
      • mSymbol
      • mLinkage
    • Methods:
      • dumpAsOperand()
    • Derived:
      • GlobalVariable
      • Function
  • GlobalVariable: public GlobalValue
    • Data:
      • ConstantValue* mInitVAlue
      • size_t mAlignment
  • Argument: public TrackableValue
    • Data:
      • mFunc
      • mLabel
  • Function: public GlobalValue
    • Data:
      • mArguments
      • mBlocks
  • BasicBlock
  • Module
    • Data:
      • mFunctions
      • mGlobalVariables
  • IRBuilder

MIR Machine IR

更接近底层, 此处将 MIR 抽象/定义在面向特定的体系结构和汇编语言. 要对所面向的计算机体系结构 和 汇编语言规范 进行表示, 并最终翻译成汇编语言.

ISA 指令集体系结构

微体系结构

翻译在追求等价性之外, 也追求"性能", 即翻译的好坏的问题. 一般是先根据上层语言的语法语义, 一比一对照翻译成下层语言表示, 然后再在下层语言表示上做程序的等价变换.

当然 翻译本身就是一种等价变换, 不过翻译是跨语言的, 而语言内的等价变换是不跨语言的, 因此比在翻译的同时执行优化变换, 分离了两个步骤, 更加清晰方便.

变换同时意味着信息的损失, 因而我们要设计有足够的表达能力的中间表示, 期以尽可能多地保留上层语言表示中的信息. 另一方面, 信息也可以从对程序的表示进行分析获得, 往往对应与在上下语言变换中基本没有损失的信息, 可以不必在翻译时特地存储该信息, 可以在翻译完成后进行分析获得.

这样做的根本思想是解耦合, 将复杂问题拆解和化简, 以更有效地解决问题. (也是抽象)

人类思维 与 机器规则 的交互, 几乎永恒的问题.