2023年华为毕昇杯技术培训会笔记

第一场1-编译原理概述

第一场2-中间代码和目标代码的优化（基础篇）

中间代码的优化

例子：快速排序算法

将上述红框中的代码片段转化为三地址代码：

把这30行代码按照goto语句划分为块，如下图：

一共是6个基本块，其中包含3个循环。

全局公共子表达式

寻找全局公共子表达式（Common subexpression）。如果某个值E在出现之前必然被计算过，且E在后续没有被修改，那么E的出现就是一个公共子表达式。

如下图，t7可用t6代替，t10可被t8代替。那么t7和t10就不必再被计算。

放眼全局看，也可以找到一些全局公共子表达式t6、t7、t8、t10：

消除全局公共子表达式以后，就是下图：

复制传播

消除复制传播。如B5中的x可以被消除：

死代码消除

在上面消除复制传播时，消除B5中的x后，x = t3这句话便成为死代码，可以被消除。

强度削减

原来的B3中t4 = 4*j，而在这句话之前j = j - 1，则直接可以变为t4 = t4 - 4，将乘除变为了加减。

同样B2中的t2 = 4*i，也可以进行削减。

在B4中，可以把i>=j换为t2>=t4。如此削减，便使得i和j成为死代码，即可删除B1、B2、B3中对i和j的赋值。（只针对上图来说）

数据流抽象

上述例子有几个代码块，抽象出来就是下图：

其数据流的例子：

• B1、B2、B3输出的x均为3，那么B的输入的x就是3
• B1、B3输出的y为4，而B2输出的y为5，那么B的输入的y就不确定
• B1输输出的z不确定，那么B的输入的z就不确定

如果某个值d经过某个块B后没被修改，则说明d的定值到达B，B没有杀死d，否则认为B杀死了d，如下图所示：

后面看不下去了，先记录到这。

第一场3-LLVM基础介绍