精华内容
下载资源
问答
  • 代码优化和目标代码生成10.1 代码优化概念1) 基本概念2) 优化的种类3) 数据流方程10.2 代码优化技术10.2.1 局部优化1) 基本块概述划分基本块基本块划分举例2) 流图3) 基本块的 DAG 表示DAG 扩充四元式的 DAG 表示4)...

    文章原理
    https://gitee.com/fakerlove/fundamentals-of-compiling

    10. 代码优化和目标代码生成

    10.1 代码优化概念

    1) 基本概念

    「优化」

    • 对程序进行各种等价变换,使得从变换后的程序出发,能生成更有效的目标代码。
      • 等价:不改变程序的运行结果
      • 有效:目标代码运行时间短,占用存储空间小

    「遵循的原则」

    • 等价原则:优化不应改变程序运行的结果
    • 有效原则:使优化后所产生的目标代码运行时间较短,占用的存储空间较小
    • 合算原则:应尽可能以较低的代码取得较好的优化效果

    「优化的级别」

    • 局部优化、循环优化、全局优化

    2) 优化的种类

    「总体列举」

    • 删除多余运算(删除公用子表达式)
    • 合并已知量
    • 复写传播
    • 删除无用赋值
    • 代码外提
    • 强度消弱
    • 变换循环控制条件

    原代码

    void quicksort(m, n);
    int m, n;
    {
        int i, j, v, x;
        if(n <= m) return;
        i = m-1, j = n, v = a[n];
        while(1) {
            do i = i+1; while(a[i] < v);
            do j = j-1; while(a[j] > v);
            if(i >= j) break;
            x = a[i], a[i] = a[j], a[j] = x;
        }
        x = a[i], a[i] = a[n], a[n] = x;
        quicksort(m, j); quicksort(i+1, n);
    }
    123456789101112131415
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UfkDSUL0-1597803590572)(media/15909049783041.jpg)]

    删除公共子表达式

    T1 = 4*i
    T2 = 4*i
    
    T1 = 4*i
    T2 = T1
    12345
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hzBUbODw-1597803590575)(media/15909050499873.jpg)]

    复写传播

    T4 = T2
    T3 = T4 + 1
    
    T4 = T2
    T3 = T2 + 1
    12345
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HOhu3OD2-1597803590576)(media/15909050886615.jpg)]

    删除无用赋值

    T4 = T2 // T4 无用
    T3 = T2 + 1
    
    T3 = T2 + 1
    1234
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b467uUXS-1597803590578)(media/15909051323640.jpg)]

    强度削弱

    i = i + 1
    T2 = 4 * i
    
    i = i + 1
    T2 = T2 + 4
    12345
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PiauoZkL-1597803590579)(media/15909052980900.jpg)]

    删除归纳变量

    • 如下例所示,i、j 可以被 T2、T4 取代,因此删除 i、j

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y3W0UfuJ-1597803590581)(media/15909053894704.jpg)]

    3) 数据流方程

    入口活跃变量 = 出口活跃变量 - 被定义的变量 + 被引用的变量

    10.2 代码优化技术

    10.2.1 局部优化

    「局部优化」

    • 局限于基本块范围内的优化

    1) 基本块

    概述

    「基本块」

    • 程序中一顺序执行语句序列,只有一个入口和一个出口。
    • 入口就是第一个语句,出口就是最后一个语句。

    「定值 & 引用」

    • 对三地址语句为 x := y + z,称 x 定值并引用 y 和 z

    「活跃的」

    • 基本块中的一个名字在程序中的某个给定点是活跃的,指如果在程序中(本基本块 + 其它基本块)它的值在该点以后被引用
    划分基本块

    一、找出中间语句程序中各个基本块的入口语句(三地址语句)

    • 程序第一个语句
    • 能由条件转移语句或无条件转移语句转移到的语句
    • 紧跟在条件转移语句后面的语句

    二、对以上求出的每个入口语句,确定其所属的基本块

    • 入口语句 => 下一入口语句的前一天语句
    • 入口语句 => 转移语句
    • 入口语句 => 停语句

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mpIO88Da-1597803590581)(media/15909083055387.jpg)]

    三、凡未被纳入某一基本块中的语句,可以从程序中删除

    基本块划分举例

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xuc7X8BR-1597803590582)(media/15909083775691.jpg)]

    2) 流图

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-swFvK3L6-1597803590583)(media/15909084792988.jpg)]

    • 基本块为结点,程序第一条语句所在基本块是首结点
    • 连边
      • B2 紧接着 B1 之后执行,且 B1 最后一条语句不是无条件转移语句,则 B1 => B2
      • B1 最后一条语句是(无)条件转移语句,转移到 B2 的第一条语句,则 B1 => B2

    3) 基本块的 DAG 表示

    DAG 扩充
    • 在 DAG 上增加标记和附加信息
      • **「叶结点」**以标识符或常数作为标记,表示该结点代表该变量或常数的值
      • **「内部结点」**以运算符作为标记,表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果
      • **「附加」**各个结点可能附加一个或多个标识符表示这些变量具有该结点所代表的值
        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hv24PS5u-1597803590583)(media/15909143499311.jpg)]
    四元式的 DAG 表示

    「0型:A := B」(:=, B, -, A)
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xn70O66u-1597803590584)(media/15909144376409.jpg)]

    「0型:goto (s)」(j, -, -, (s))
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LBAbBjE0-1597803590585)(media/15909147155150.jpg)]

    「1型:A := op B」(op, B, -, A)
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1m1iUJ1U-1597803590585)(media/15909147956004.jpg)]

    「2型:A := B op C」(op, B, C, A)
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CJE4Jp1R-1597803590585)(media/15909147785614.jpg)]

    「2型:A := B[C]」(=[], B, C, A)
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kPvtfgHU-1597803590586)(media/15909147585488.jpg)]

    「2型:if B rop C goto (s)」(jrop, B, C, (s))
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KZR4bfsM-1597803590587)(media/15909147313087.jpg)]

    「3型:D[C] := B」([]=, B, D, C)
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2af0hVly-1597803590587)(media/15909146958961.jpg)]

    4) 基本块的优化算法

    优化算法概述
    • 一个基本块,可用一个 DAG 来表示
    • 对基本块中每一条四元式代码,依次构造对应的 DAG 图,最后基本块中所有四元式构造出来的 DAG 连成整个基本块的 DAG
    • 具体流程
      • 准备操作数的结点
      • 合并已知量
      • 删除公共子表达式
      • 删除无用赋值
    示例

    「示例」
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k7Q5AeGA-1597803590588)(media/15909150817087.jpg)]

    「优化结果」
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7csYyJ3W-1597803590588)(media/15909151334061.jpg)]

    构造基本块的 DAG 算法

    参考上述示例,引入下述的具体过程。

    • 引入函数 Node,保存和计算 DAG 中标识符与结点的对应关系
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dHQ0nMSp-1597803590589)(media/15909152038160.jpg)]
    • 对基本块中每一四元式,依次执行以下步骤
      1. 准备操作数的结点
      2. 合并已知量
      3. 删除公共子表达式
      4. 删除无用赋值

    「1. 准备操作数的结点」

    • 如果 Node(B) 无定义,则构造一标记为 B 的叶结点并定义 Node(B) 为这个结点
      • 如果四元式为 0 型(A := B),则记 Node(B) = n,转 4
      • 如果四元式为 1 型(A := op B),转 2(1)
      • 如果四元式为 2 型(A := B op C)
        • 如果 Node© 无定义,则构造一标记为 C 的叶结点并定义 Node© 为这个结点
        • 转 2(2)

    「2. 合并已知量」

    • 如果 Node(B) 是标记为常数的叶结点,转 2(3),否则转 3(1)
    • 如果 Node(B) 和 Node© 都是标记为常数的叶结点,则转 2(4),否则转 3(2)
    • 执行 op B(合并已知量),令得到的新常数为 P
      • 如果 Node(B) 是处理当前四元式时新构造出来的结点,则删除它
      • 如果 Node§ 无定义,则构造一用 P 作标识符的叶结点 n,置 Node§ = n
      • 转 4
    • 执行 B op C(合并已知量),令得到的新常数为 P
      • 如果 Node(B) 或 Node© 是处理当前四元式时新构造出来的结点,则删除它
      • 如果 Node§ 无定义,则构造一用 P 作标记的叶结点 n,置 Node§ = n
      • 转 4

    「3. 删除公共子表达式」

    • 检查 DAG 中是否已有一结点,其唯一后继为 Node(B),且标记为 op,即公共子表达式
      • 如果没有,则构造该结点 n
      • 否则,把已有的结点作为它的结点并设该结点为 n,转 4
    • 检查 DAG 中是否已有一结点,其左后继为 Node(B),右后继为 Node©,且标记为 op,即公共子表达式
      • 如果没有,则构造该结点 n
      • 否则,把已有的结点作为它的结点并设该结点为 n,转 4

    「4. 删除无用赋值」

    • 如果 Node(A) 无定义,则把 A 附加在结点 n 上并令 Node(A) = n
    • 否则,先把 A 从 Node(A) 结点上的附加标识符集中删除
      • 如果 Node(A) 为叶结点,则其 A 标记不删除
      • 把 A 附加到新结点 n 上并置 Node(A) = n,转处理下一四元式

    「信息总结」

    • 在基本块外被定值并在基本块内被引用的所有标识符,就是作为叶子结点上标记的那些标记符
    • 在基本块内被定值并且该值在基本块后面可以被引用的所有标识符,就是 DAG 各结点上的那些标记或者附加标识符

    10.2.2 循环优化

    循环优化,主要有三大措施:

    1. 代码外提
    2. 强度消弱
    3. 删除归纳变量(变换循环控制条件)

    1) 循环不变运算

    • 具体定义
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TWOgVwUZ-1597803590589)(media/15922360982245.jpg)]
    • 寻找算法
      • 反复遍历
        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1qgt8OxV-1597803590590)(media/15922361131887.jpg)]

    2) 代码外提

    • 找到不变运算
    • 检查是否符合代码外提条件
    • 保持次序前提下提出代码
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A2EYJWyY-1597803590590)(media/15922361774720.jpg)]
    • 举例
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YXukRpO6-1597803590591)(media/15922362011731.jpg)]

    3) 强度消弱

    • 核心思想
      • 将程序中执行时间较长的运算转换为执行时间较短的运算
      • 例如将乘法换成加法
    • 举例
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pQft93vj-1597803590591)(media/15922363373271.jpg)]
    • 适用范围
      • 强度消弱通常是针对循环控制变量有先行关系的变量赋值进行
      • 经过强度消弱后,循环中可能出现一些新的无用赋值
      • 对于消弱下标变量地址计算的强度非常有效

    4) 删除归纳变量

    归纳变量
    • 基本归纳变量、归纳变量的定义
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qDIaUpv1-1597803590592)(media/15922364596031.jpg)]
    具体算法
    • 具体算法
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tVwzIdel-1597803590593)(media/15922364887129.jpg)]
    • 举例
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ce3UoWIS-1597803590593)(media/15922365342326.jpg)]

    10.3 目标代码生成概念

    1) 任务

    将分析、翻译、优化后的中间代码变换成目标代码

    2) 输入

    • 源程序的中间表示,以及符号表中的信息
    • 类型检查均已完成

    3) 输出

    • 绝对指令代码:能够立即执行的机器语言代码,所有地址已经定位
    • 可重新定位指令代码:机器语言模块,需要与运行程序链接才能执行
    • 汇编指令代码:需要汇编程序转换成可执行机器语言代码

    10.4 目标代码生成概念

    10.4.1 抽象计算机模型

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y8MtflU7-1597804366666)(media/15919406135931.jpg)]

    其中 (M) 表示主存中 M 位置的数据。

    其它指令

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rC1S3AZW-1597804366671)(media/15919407065932.jpg)]

    10.4.2 代码生成

    1) 代码生成原则

    • 以基本块为单位生成目标代码
      • 依次把四元式的中间代码变换成目标代码
      • 在基本块的范围内考虑如何充分利用寄存器
      • 进入基本块时,所有寄存器空闲
      • 离开基本块时,把存在寄存器中的现行的值存回主存中,释放所有寄存器
      • 不特别说明,所有说明变量在基本块出口之后均为非活跃变量
    • 在一个基本块的范围内考虑充分利用寄存器
      • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SDbotCgP-1597804366673)(media/15919411349479.jpg)]

    2) 待用信息和活跃信息

    概念解释

    活跃信息 - 将来会不会被引用

    待用信息 - 将来在什么地方会被引用

    符号表示
    • 二元组 (x, x) 表示变量的待用信息和活跃信息
      • 第 1 元: i 表示将会在第 i 行被引用、^表示非待用
      • 第 2 元: y 表示活跃,^表示非活跃
    • 信息变化
      • (x, x) -> (x, x),用后者更新前者
        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bsGrMhJY-1597804366677)(media/15919417529214.jpg)]
    • 计算方法
      • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0sbN0uUg-1597804366679)(media/15919419915583.jpg)]

    3) 变量地址、寄存器描述

    目的

    推出 AVALUE、RVALUE 目的:

    • 四元式指令:指令中各变量在将来会被使用的情况
    • 变量:每个变量现行值的存放位置
    • 寄存器:每个寄存器当前的使用情况
    概念
    • AVALUE(变量地址描述数组)
      • 动态记录各变量现行值的存放位置
      • AVALUE[A] = {R1, R2, A}
    • RVALUE(寄存器描述数组)
      • 动态记录各寄存器的使用信息
      • RVALUE[R] = {A, B}

    注意,对于四元式 A:=B

    • 如果 B 的现行值在某寄存器 R i R_iR**i 中,则无须生成目标代码
    • 只须在 RVALUE(R i R_iR**i) 中增加一个A,并把 AVALUE(A) 改为 R i R_iR**i

    4) 代码生成算法

    算法描述
    • 总体流程
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b6ZkcNxP-1597804366681)(media/15919427503801.jpg)]
    • 寄存器分配算法
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vBHO68Gy-1597804366681)(media/15919430154559.jpg)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xT7MTxWG-1597804366682)(media/15919431983786.jpg)]

    算法举例
    • 为基本块生成代码示例

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RPHFrtRj-1597804366683)(media/15919441467599.jpg)]

    10.4.3 DAG的目标代码

    作用:重排中间代码,减少目标代码

    算法:

    1. 构建 DAG,结点标记写在结点圆圈中,叶结点未编号,内部结点的编号写在各结点下面
    2. 倒序填写中间代码编号,找到无父节点的结点,向左进行递归拓扑,遇到子结点或无法拓扑则停止

    举例:

    • 中间代码
    T1 := A+B
    T2 := A-B
    F := T1*T2
    T1 := A-B
    T2 := A-C
    T3 := B-C
    T1 := T1*T2
    G := T1*T3
    12345678
    
    • DAG图
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wm1FP2at-1597804366683)(media/15919508975356.jpg)]
    • 节点重排
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D9O25T5T-1597804366684)(media/15919509276131.jpg)]
    展开全文
  • 编译原理代码优化

    2021-10-07 21:54:55
    常用的优化方法 删除公共子表达式 删除无用代码 常量合并 代码移动 强度削弱 删除归纳变量 基本块的优化: 局部优化技术大部分都是将基本块转为有向无环图(DAG). 每个语句s都对应一个内部结点N 结点N的标号是s中...


    前言

    定值: 对变量的赋值即为定值,这将会kill掉之前对变量的定值。
    引用:对变量的使用。

    活跃范围: 从定值到最后一次引用即为变量的活跃范围。

    a = ...		//	10
    ....
    .... = a+1	//	20
    ...  =
    a = ...		//	25
    ...
    .... = a+2	//	40
    

    如上面代码所示,10对a进行了赋值/定值,20对a的值进行了最后一次使用,因此a的活跃范围是{10,20}。而后a的值在25被再次定值,那么a之前的定值无法被使用,也就是被kill掉。a的新值在40处被使用,a的活跃范围就是{10,20},{25,40}。

    一、基本块的优化

    局部优化技术大部分都是将基本块转为有向无环图(DAG).

    有向无环图的好处就是可以明确变量之间的依赖关系和指令执行顺序的关系。

    每个语句s都对应一个内部结点N

    • 结点N的标号是s中的运算符;同时还有一个定值变量表被关联到N ,表示s是在此基本块内最晚对表中变量进行定值的语句
    • N的子结点是基本块中在s之前、最后一个对s所使用的运算分量进行定值的语句对应的结点。

    基于DAG删除无用代码:
    删除所有没有附加活跃变量(活跃变量是指其值可能会在以后被使用的变量)的根结点(即没有父
    结点的结点) 。

    在这里插入图片描述

    二、数据流分析

    1.到达-定值分析 (Reaching-Definition Analysis)

    定值 (Definition) :变量x的定值是(可能)将一个值赋给x的语句。 如果某个变量x的一个定值d到达点p,在点p处使用的x的值可能就是由d最后赋予的。

    计算方法:
    在这里插入图片描述
    引用-定值链(Use-Definition Chains),即ud链,对于变量的每一次引用,到达该引用的所有定值都在该列表中。

    ud链的核心在于,可以通过该链,明确当前使用的链,在哪里被定值,被定值是否是常量等。

    应用:

    1. 循环不变计算的检测
      如果表达式的运算分量是常数,或者所有定值点都在循环外部,则可将该表达式标记为循环不变。可以提到循环外部。
    2. 常量合并
    3. 判定变量x在p点上是否未经定值就被引用
    4. 强度削弱

    1.1 强度削弱

    强度削弱比较复杂,展开描述:
    强度削弱利用了归纳变量和到达定值分析的结果。
    对于一个变量x ,如果存在一个正的或负的常量c ,使得每次x被赋值时,它的值总是增加c ,则称x为归纳变量。

    计算方法:
    寻找L中只有一次定值的变量k,它具有下面的形式:k=c′×j+d′。其中c′和d′是常量,j是基本的或非基本的归纳变量.

    效果:
    在这里插入图片描述

    2.活跃变量分析 (Live-Variable Analysis)

    对于变量x和程序点p,如果在流图中沿着从p开始的某条路径会引用变量x在p点的值,则称变量x在 点p是活跃(live)的,否则称变量x在点p不活跃(dead)。

    活跃变量分析的核心在于,在寄存器分配时,同时活跃(即为冲突)的变量分配到不同的寄存器。
    此外,如果变量是不冲突的,那么可以进行寄存器合并,但是寄存器合并时,会导致寄存器的占用时间增长,而导致存在寄存器溢出,需要降寄存器写回内存的风险。

    计算方法:
    在这里插入图片描述

    3.定值引用链分析

    定值-引用链:设变量x有一个定值d,该定值所有能够到达的引用u的集合称为x在d处的定值-引用链,简称du链。

    1. 删除无用赋值
      如果定值之后,再也没有被引用,那么就是无用定值/赋值,可以删除。

    2. 基本块分配寄存器
      分配寄存器时,优先选择不后续不再被引用的寄存器。

    此外,在进行寄存器分配时,同时活跃的变量,即为“冲突”的,不可以将其放入同一个寄存器。
    通过画出冲突图,利用图着色算法,对寄存器进行分配。

    4.可用表达式分析 (Available-Expression Analysis)

    删除公共表达式:如果一个表达式在程序的每个分支上都进行了计算,那么在分支的汇聚出口,我们可以直接使用该表达式结果。

    在点 p上,x op y已经在之前被计算过,不需要重新计算。

    计算方法:
    在这里插入图片描述
    用途:

    1. 消除全局公共子表达式
      在这里插入图片描述
    2. 进行复制传播
      在这里插入图片描述

    5.支配节点树(Dominator Tree)

    如果从流图的入口结点到结点n的每条路径都经过结点d,则称结点d支配(dominate)结点n,记为d dom n。

    通过支配节点树,我们可以分析程序的必经路径和必经路径边界信息。

    利用支配节点树的边界信息,可以产生SSA表达式的phi节点。

    计算方法:
    在这里插入图片描述

    支配结点树的例子:
    在这里插入图片描述

    总结

    常用的优化方法

    • 删除公共子表达式 : 可用表达式
    • 复制传播 : 可用表达式
    • 删除无用代码:定值引用链
    • 常量合并:引用定值链
    • 代码移动:引用定值链
    • 强度削弱:引用定值链
    • 删除归纳变量:引用定值链

    欢迎关注我的公众号《处理器与AI芯片》

    展开全文
  • 代码优化: 概述: 目的:提高代码运行效率,占用更少空间 实质:代码之间的等价变换 优化概念: 优化等级: 源程序级 程序员做的代码优化 中间代码级,主要优化内容 编译程序优化部分 目标代码级 优化代价: ...

    代码优化:

    概述:

    • 目的:提高代码运行效率,占用更少空间
    • 实质:代码之间的等价变换

    优化概念:

    • 优化等级:
      • 源程序级 程序员做的代码优化
      • 中间代码级,主要优化内容 编译程序优化部分
      • 目标代码级
    • 优化代价:
      • 优化算法的复杂度,即编程难易程度及算法时间复杂度
    • 优化代码和优化程度的关系:
      在这里插入图片描述手工水平为最优化代码,也就是汇编
    • 优化的分类:
      • 局部优化,针对一段顺序执行的语句序列的优化
        • 优化方法:
          • 合并已知量
          • 删除公共子表达式
          • 变量传播与无用赋值删除

    在这里插入图片描述在这里插入图片描述对于常量运算,可以直接在编译阶段运算出来,给运行阶段提高速度

    在这里插入图片描述删除重复运算,使用赋值操作替代重复的运算操作
    在这里插入图片描述我们可以发现,红色代码部分的左值是没有作为操作数 或者 重复赋值被覆盖了,所以可以将它们删去。

    循环优化:

    在这里插入图片描述在这里插入图片描述在这里插入图片描述这里有不变部分,T3和T6,主要是为了计算A,B数组的不变部分(参考数组的定义),这就需要我们将代码外提
    在这里插入图片描述这样减少了200次赋值操作
    在这里插入图片描述首先进行块内优化,将T1和T4合并为一个,然后观察两个的变化发现,规律是每次加10
    在这里插入图片描述将乘法操作同义替换为加法操作,有利于计算机的运算

    在这里插入图片描述在这里插入图片描述通过使用T1的每次加10的规律,作为控制变量,这样就删去了i变量

    完成循环优化,做局部优化

    局部优化:

    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述入口包括:1,3,6,10,根据划分得到

    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述将op施加在B上,得到的值由n2代表,再将A附加在n2上面,表示运算出来的结果,就是A的值
    以下为各种类型的四元式通过DAG的表示方式

    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    对于一个基本块,应该怎么操作其对于的DAG图:

    在这里插入图片描述
    当A有定义:

    • A为附加标记,将A拿掉,在附加当当前结点上
    • A为标记,不拿掉A

    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    当程序到达了第三步,表示常量运算已经运算完了,后面的运算都是需要变量参与的

    3.1步是通过一元运算中存在变量运算到达的

    3.2步是通过二元运算中存在变量运算到达的

    到了第四步,表示运算的结果,要么找到了,要么建好了
    在这里插入图片描述
    其实主要就是做了下面几件事:
    1,准备操作数结点

    2,合并常数量

    3,删除公共子表达式

    4,删除无用赋值

    在这里插入图片描述在这里插入图片描述
    创建3.14结点,附加上T0,创建2结点,搜索T0结点,运算得到6.28,删除2结点,将T1附加到6.28上

    在这里插入图片描述
    添加两个结点R,r,父节点进行加法操作,并将T2附在父节点上
    在这里插入图片描述在这里插入图片描述
    运算完6,得到6.28,将T3附到n2上

    在这里插入图片描述
    添加T5*T6,发现需要附上B,发现B有定义了,但是为附加标记,可以删除,为附加标记,表示的就是一个取值操作,但是如果是标记就表示需要参与运算了

    我们只需要将DAG图还原就得到了优化后的代码:按n的顺序还原
    在这里插入图片描述在这里插入图片描述
    当T0在后面不需要使用了就可以优化了
    我们可以在退出这个基本块之前将局部变量重新命名,这样当下一次基本块优化时,可以继续使用T0,Tn

    在这里插入图片描述

    展开全文
  • 代码生成的主要任务 指令选择 选择适当的__目标机指令__来实现__中间表示(IR)__语句 例: 三地址语句:x = y+z 目标代码 LD R0 , y:把的值加载到寄存器中 AD R0 , R0 , z:z加到上 R0 上 ST , x, R0:把 R0的值...

    代码生成器的主要任务

    一、指令选择

    • 选择适当的目标机指令来实现中间表示(IR)语句,
    • 例如:三地址语句 x = y + z
      目标代码:
      
      LD R0, y      /* 把y的值加载到寄存器R0中*/
      ADD R0, R0, z /* z加到R0上*/
      ST x, R0      /* 把R0的值保存到x中*/
      
    • 如上,直接进行生成,会产生一些冗余指令。目标代码需要进一步优化。

    二、寄存器分配和指派:

    • 把哪个值放在哪个寄存器中

    三、指令排序:

    • 按照什么顺序来安排指令的执行

    一个简单的目标机模型

    三地址机器模型:

    • 加载、保存、运算、跳转等操作
    • 内存按字节寻址
    • n个通用寄存器 R 0 , R 1 , … , R n − 1 R_0, R_1, …, R_{n-1} R0,R1,,Rn1
    • 假设所有的运算分量都是整数
    • 指令之间可能有一个标号

    目标机器的主要指令

    • 加载指令 LD dst, addr

      • LD r, x
      • LD r1, r2
    • 保存指令 ST x, r

    • 运算指令 OP dst, src1, src2

    • 无条件跳转指令 BR L

    • 条件跳转指令 Bcond r, L

      • 例: BLTZ r, L

    寻址模式

    • 变量名a

      • 例如:LD R1, a,即R1 = contents(a),将地址 a 中的内容放到寄存器 R1
    • a(r),a是一个变量,r是一个寄存器

      • 例如:LD R1, a(R2),即R1 = contents(a + contents(R2))
    • c(r),c是一个整数

      • 例如:LD R1, 100(R2),即R1 = contents(contents(R2) + 100),表示寄存器 R2 中存放的地址,加上整数c,其表示的地址所存放的内容。
    • ∗r,在寄存器r的内容所表示的位置上存放的内存位置

      • 例如:LD R1, *R2,即R1 = contents(contents(contents(R2))),这是间接寻址模式
    • ∗c(r),在寄存器r中内容加上c后所表示的位置上存放的内存位置

      • 例如:LD R1, *100(R2),即R1 = contents(contents(contents(R2) + 100))
    • KaTeX parse error: Expected ‘EOF’, got ‘#’ at position 1: #̲c,

      • 例如LD R1, #100,即R1 = 100。

    指令选择

    运算语句的目标代码

    • 三地址语句:x = y - z

    • 目标代码:

      LD R1 , y        // R1 = y
      LD R2 , z        // R2 = z
      SUB R1 , R1 , R2 // R1 = R1 - R2
      ST x , R1        // x = R1
      
    • 尽可能避免使用上面的全部四个指令,如果:

      • 所需的运算分量已经在寄存器中了
      • 运算结果不需要存放回内存

    数组寻址语句的目标代码

    • 三地址语句:b = a[ i ](a是一个实数数组,每个实数占8个字节)
      • 目标代码:
      LD R1 , i      // R1 = i
      MUL R1 , R1, 8 // R1=R1 * 8
      LD R2 , a(R1)  // R2=contents ( a + contents(R1) )
      ST b , R2      // b = R2
      
    • 三地址语句:a [ j ] = c(a是一个实数数组,每个实数占8个字节)
      • 目标代码:
      LD R1 , c       // R1 = c
      LD R2 , j       // R2 = j
      MUL R2 , R2 , 8 //R2 = R2 * 8
      ST a(R2) , R1   // contents(a+contents(R2))=R1
      

    指针存取语句的目标代码

    • 三地址语句:x = *p
      • 目标代码:
      LD R1, p      // R1 = p
      LD R2, 0 (R1) // R2 = contents ( 0 + contents (R1) )
      ST x , R2     // x = R2
      
    • 三地址语句:*p = y
      • 目标代码:
      LD R1 , p    // R1 = p
      LD R2 , y    // R2 = y
      ST 0(R1), R2 //contents ( 0 + contents ( R1 ) ) = R2
      

    条件跳转语句的目标代码

    • 三地址语句:if x < y goto L
      • 目标代码:
      LD R1 , x        // R1 = x
      LD R2 , y        // R2 = y
      SUB R1 , R1 , R2 // R1=R1 - R2
      BLTZ R1 , M      // if R1 < 0 jump to M
      
      • M是标号为L的三地址指令所产生的目标代码中的第一个指令的标号。

    过程调用和返回的目标代码
    静态区存储分配

    • 方法调用
      • 三地址语句:call callee
      • 目标代码
      ST callee.staticArea, #here + 20 //即callee的活动记录在静态区中的起始位置
      BR callee.codeArea,  //即calle的目标代码在代码区中的起始位置
      
    • 方法返回
      • 三地址语句:return
      • 目标代码
      BR * callee.staticArea // 间址,返回地址在 callee 栈帧底部
      

    栈式存储分配

    • 方法调用
      • 三地址语句:call callee
      • 目标代码
      ADD SP, SP, #caller.recordsize 
      ST 0(SP), #here+16  // 把返回地址压到被调过程的栈帧底部
      BR callee. code Area
      
    • 方法返回
      • 三地址语句:return
      • 目标代码
      	被调用过程:BR* 0(SP)
      	调用过程:SUB SP, SP, #caller.recordsixe
      

    寄存器的选择

    三地址语句的目标代码生成

    对每个形如x = y op z的三地址指令I,执行如下动作:

    • 调用函数 getreg(I)来为x、y、z选择寄存器,把这些寄存器称为 R x R y R z R_x R_y R_z RxRyRz
    • 如果 R y R_y Ry 中存放的不是y ,则生成指令“LD    Ry ,    y′ ′”。y′ 是存放y的内存位置之一
    • 类似的,如果Rz中存放的不是z,生成指令“LD    Rz ,   z ′ ”
    • 生成目标指令“OP    Rx ,    Ry ,    Rz ”

    寄存器描述符和地址描述符

    寄存器描述符(register descriptor):

    • 记录每个寄存器当前存放的是哪些变量的值

    地址描述符(address descriptor):

    • 记录运行时每个名字的当前值存放在哪个或哪些位置
    • 该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
    • 这些信息可以存放在该变量名对应的符号表条目中

    基本块的收尾处理

    对于一个在基本块的出口处可能活跃的变量x

    • 如果它的地址描述符表明它的值没有存放在x的内存位置上,则生成指令“ST x, R” ( R是在基本块结尾处存放x值的寄存器)

    管理寄存器和地址描述符

    对于指令LDR, x":

    • 修改R的寄存器描述符,使之只包含x
    • 修改x的地址描述符,把R作为新增位置加入到x的位置集合中
    • 从任何不同于x的地址描述符中删除R

    对于指令"OP Rx, Ry ,Rz,":

    • 修改Rx的寄存器描述符,使之只跑含x
    • 从任何不同于Rx的寄存器描述符中删除x
    • 修改x的地址描述符,使之只包含位置Rx
    • 从任何不同于x的地址描述符中删除Rx

    对于指令“ST x, R”:

    • 修改x的地址描述符,使之包含自己的内存位置

    对于复制语句x=y,如果需要生成加载指令"LD Ry, y’"则:

    • 修改Ry的寄存器描述符,使之只包含y
    • 修改y的地址描述符,把Ry作为新增位置加入到y的位置集合中
    • 从任何不同于y的变量的地址描述符中删除Ry
    • 修改Ry的寄存器描述符,使之也包含x
    • 修改x的地址描述符,使之只包含Ry

    窥孔优化

    • 窥孔(peephole)是程序上的一个小的滑动窗口

    • 窥孔优化是指在优化的时候,检查目标指令的一个滑动窗口(即窥孔) ,并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列。

    • 也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量。

    具有窥孔优化特点的程序变换的例子

    • 冗余指令删除
      • 例如:消除冗余的加载和保存指令
      • 例如:消除不可达代码,一个紧跟在无条件跳转之后的不带标号的指令可以被删除。
    • 控制流优化
      • 在代码中出现跳转到跳转指令的指令时,某些条件下可以使用一个跳转指令来代替。
      • 如果不再有跳转到L1的指令,并且语句L1: goto L2之前是一个无条件跳转指令,则可以删除该语句。
    • 代数优化
      • 代数恒等式:消除窥孔中类似于x=x+0或x=x*1的运算指令。
      • 强度削弱:
        对于乘数(除数)是2的幂的定点数乘法(除法) ,用移位运算实现代价比较低;
        除数为常量的浮点数除法可以通过乘数为该常量倒数的乘法来求近似值。
    • 机器特有指令的使用
      • 充分利用目标系统的某些高效的特殊指令来提高代码效率。
      • 例如:INC指令可以用来替代加1的操作。
    展开全文
  • 将开销较大的操作采用等价但是开销相对较少的操作进行替代的一种优化方法。 就是不用每次循环生成多余空间,在这里是这样的 注:归纳变量官方解释 循环中的一个变量,其值在每一次循环迭代过程中增加(或...
  • 声明:本系列文章,是根据中国大学MOOC网 哈工大的编译原理 这门课学习而成的学习笔记。一、流图基本块(Basic Block)基本块是满足下列条件的最大的连续三地址指令序列控制流只能从基本块的第一个指令进入该块。也...
  • 编译原理课程设计--C语言编译器实现甘肃政法学院编译原理课程设计题 目 C语言编译器实现计算机科学学院计算机科学与技术专业10 级 计本 班学 号: 201081010137姓 名: 杨青虎指导教师: 李 霞完成时间: 2013 年 6 ...
  • 最近在学习微机原理,里面涉及到编译优化的问题,又去重新看了看龙书的语法分析部分。之前学习的时候只是知道first和follow集合怎么计算,但是没有很明白背后的原理。想起轮子哥的一句话:要理解一个东西最好的办法...
  • 学完编译原理已经一年了,也有半年被因为学其他东西而没空继续深入学习编译原理。现在终于有机会继续学习了。首先回顾下,编译原理考试第一题的答案。就是翻译的步骤。对于编译,第一步是词法分析。也就是分出一个个...
  • 编译原理

    2021-06-07 06:49:04
    内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等...
  • 文章目录1 实验目的和内容1.1 实验目的1.2 实验内容1.3 实验要求2 设计思想2.1 语义规则2.2 递归下降翻译2.3 递归下降子程序伪代码3 算法流程4 源程序5 调试数据5.1 测试样例一5.2 测试样例二5.3 测试样例三5.4 ...
  • N - DAG优化编译原理练习) Input 输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数 之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * / 例如:A=B+C Output 通过构造...
  • 为了便于优化处理,作为中间代码,设一张指示表(间接码表) 四元式 四元式主要由四部分组成: (OP,arg1,arg2,result) 其中,OP是运算符,argl、arg2分别是第一和第二个运算对象,result是编译
  • 本系列为个人编译原理学习笔记,谬误之处恳请高人指点,感激不尽!内容整理自西安电子科技大学 王小兵、张南、鱼滨老师的编译原理课程。编译器的工作步骤在开始说任何东西之前,我们先来大致看一下编译器是怎么工作...
  • (1)便于进行与机器无关的代码优化; (2)使编译程序改变目标机更容易; (3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前 端和后端的接口更清晰。 1.中间语言 1.1后缀式 1.2抽象语法树与...
  • 前几天有个朋友问我关于C语言的编译原理和编译的过程,当时我也没有说明白,今天特意在书上和网上查阅资料,简单的总结了一下关于C语言的编译原理及过程。集成开发环境是用于提供程序开发环境的应用程序,一般包括...
  • 代码优化_1 1 优化可生成()的目标代码。 A. 运行时间较短 B. 占用存储空间较小 C. 运行时间短但占用内存空间大 D. 运行时间短且占用存储空间小 2 基本块内的优化为 ( )。 A. 代码外提,删除归纳变量 B. 删除多余...
  • 编译原理C++词法简单实现
  • 简单说明: 1:这是一份简单的代码代码实现的思路说明。 参考文章: 1:NFA到DFA的转化(保证能讲明白):https://blog.csdn.net/weixin_43655282/article/details/108963761 2:高端代码实现: ...
  • 或者调研词法分析程序的自动生成工具LEX或FLEX,设计并实现一个能够输出单词序列的词法分析。 (2)通过设计调试词法分析程序,实现从源程序中分离出各种类型的单词;加深对课堂教学的理解;提高词法分析方法的...
  • 编译原理学习笔记与实践(一) 编译器 编译器是一个将源代码转换到目标机器语言的一个程序,它是一个十分复杂的系统,概括的来说,可以以一张图来描述 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来...
  • 编译原理概述——基本知识要点汇总,主要对翻译程序、编译程序、解释程序、汇编程序几个概念进行区分和总结,并对编译过程及编译程序的基本结构、编译程序的生成方法做出归纳
  • THOMPSON 算法的实现一、实验目的二、实验要求、内容三、实验设备四、实验原理(或程序框图)及步骤五、程序源代码六、实验数据、结果分析七、存在的问题与体会 一、实验目的 掌握将正规表达式转换为NFA的方法和过程...
  • 在《Java代码的编译与反编译》中,有过关于Java语言的编译和反编译的介绍。我们可以通过javac命令将Java程序的源代码编译成Java字节码,即我们常说的class...在编译原理中,把源代码翻译成机器指令,一般要经过以...
  • Java的编译原理

    2021-02-12 09:45:06
    概述java语言的"编译期"分为前端编译和...在编译原理中, 将源代码编译成机器码, 主要经过下面几个步骤:Java中的前端编译java的前端编译(即javac编译)可分为解析与填充符号表、插入式注解处理器的注解处理、分析与字...
  • 1、参考书籍:《编译原理》第三版 清华大学出版社 1、本文内容全部来源于开源社区 GitHub和以上博主的贡献,本文也免费开源(可能会存在问题,评论区等待大佬们的指正) 2、本文目的:开源共享 抛砖引玉 一起学习 3...
  • java学习编译原理

    2021-03-05 21:16:49
    我们发现中间的代码有一些代码是不需要做的,这里做代码优化。将一部分不需要的代码省略。 最后生成目标的代码,这里因为截图不是java代码,所以最后显示的目标文件是一个汇编指令。movl id3 R2,意思就是将id3的值...
  • 计算机程序编译原理学习心得《编译原理》是计算机专业的一门重要课程,正如教材:第一章的引论所述,“编译程序是现代计算机系统的基本组成部分之一”。“一个编译程序就是一个语言翻译程序,语言翻译程序把一种语言...
  • 各位好 这篇是我开坑的第一篇编译原理的博客 也是第一篇关于我学习编译原理的博客 不得不说一下 在这段时间中 尤其是上一周 和 这一周 今天已经是大二上的第十周了 这段时间我的心情是比较的down的 至于为什么down ...
  • 2020年 第52篇大型C++工程项目,都会面临编译耗时较长的问题。不管是开发调试迭代、准入测试,亦或是持续集成阶段,编译行为无处不在,降低编译时间对提高研发效率来说具有非常重要意义。一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 152,719
精华内容 61,087
关键字:

编译原理实现实现代码优化器