毕昇编译器原理与实践（华为智能计算技术丛书）

《毕昇编译器原理与实践》详细讨论了毕昇编译器的设计原理与实现，深入介绍了现代编译器设计和实践。全书共 8 章，包括编译器概述，鲲鹏处理器，编译器前端的词法分析、语法分析和语义分析，编译器中端的中间表示、中间代码生成、中间代码优化、静态单赋值形式等，编译器后端的指令选择、指令调度、寄存器分配等内容。本书重点讨论了毕昇编译器中使用的先进编译优化技术，如循环优化、自动向量化、多级存储优化和反馈式优化等，并讨论了基于 AI 的编译器自动调优等内容。为方便读者学习和掌握相关内容，书中每章都给出了可以继续深入学习的文献，并给出了丰富的习题供读者练习。

通过阅读本书，读者可以深入理解编译器设计的基本原理和实践技术、鲲鹏指令集体系结构、毕昇编译器的优化技术等内容，从而为将来从事编译器理论深入研究和工程实践打下坚实的基础。

《毕昇编译器原理与实践》可作为高等院校、科研机构等相关单位从事编译原理教学和科研的教师或研究人员的参考书，也可作为高等院校信息与计算机科学、软件工程等相关专业的本科生、研究生学习编译原理的教材或参考书，还可供对编译原理和实践等领域感兴趣的工程技术人员参考使用。

华为公司官方出品！深入解析毕昇编译器原理与设计实践。中国工程院院士郑纬民、华为ICT产品与解决方案总裁汪涛联袂作序！

PREFACE

前言

编译原理与技术是计算机科学中古老的、高度发达的，同时也是成果应用最广泛的课题之一。编译器原理涉及的知识体系非常广且繁杂，和计算机科学的许多分支学科（如形式语言与自动机、类型系统、算法设计分析、程序设计语言、最优化理论、指令集体系结构等）都有密切联系。同时，编译器工程又涉及算法数据结构、软件工程、软件测试等领域的知识，包含很多编程技巧和各种工程优化。对编译器设计者、程序员和相关领域的学习者来说，除了需要掌握扎实的编译理论知识外，全面分析和学习优秀的编译器实践也非常重要。

本书以华为毕昇编译器的具体设计和实现为例，全面讨论了现代编译器设计的基本原理和实现技术。华为公司在编译器设计与实现方面有十几年的历史，毕昇编译器就是最新发布的一款面向鲲鹏体系结构的编译器，支持 C/C++、FORTRAN 等源语言，通过引入高性能编译器算法、加速指令集、AI 迭代调优等创新技术，达到了性能极致、安全可信的设计目标； 成功支持了华为各种产品和解决方案。作为第一本深入介绍毕昇编译器设计原理和实践的书籍，希望通过本书能让更多读者深入了解毕昇编译器，共同推动国内编译器技术研究和实践的发展。

本书以毕昇编译器为主线，理论与实际相结合，通过对编译器设计原理和毕昇具体实践的详细讨论，让读者能够对现代编译器设计和实践有更深入的理解。

本书定位为“编译器原理”课程的教学参考书，其主要受众包括计算机相关专业的本科生和研究生，此外，编译器领域的从业者和对编译原理感兴趣的读者也可以参考使用。

在本书的编写过程中得到了许多支持和帮助，特此表示感谢。特别感谢华为公司Fellow 胡子昂博士在本书的撰写过程中给予的建议和支持； 感谢华为公司的谢桂磊、梁思伟、陈海波、骆能军、丁为杰、何璐等领导和业务主管对本书写作的大力支持与指导； 感谢华为公司的魏伟、张文、程伟、郭歌、彭成寒、伊金静等技术专家和同事提供相关资料与技术支持； 他们在本书撰写和修订过程中，提出了非常详尽的意见和建议，对提升本书的质量提供了非常大的帮助。感谢中国科学技术大学李曦教授、孙广中教授审阅了本书初稿； 感谢中国科学技术大学先进编译技术实验室的同学们对本书撰写工作提供的支持，尤其感谢胡霜和刘晓妍两位研究生在初稿准备中做出的极大贡献。

限于作者的知识水平和时间，书中难免有疏漏和不妥之处，恳请读者指正。

华保健高耀清

2022年6月

CONTENTS

目录

第1章编译器概述00

1.1编译器基本概念00

1.2编译器发展历史00

1.3编译器的基本功能与结构00

1.3.1前端00

1.3.2中端00

1.3.3后端00

1.4编译器的设计目标0

1.5毕昇编译器0

1.6小结0

1.7深入阅读0

1.8习题0

第2章鲲鹏处理器0

2.1概述0

2.2体系架构0

2.2.1执行状态0

2.2.2支持的指令集0

2.2.3数据类型0

2.3CPU访存原理0

2.3.1多级存储系统0

2.3.2地址空间0

2.3.3地址变换0

2.3.4存储器类型和属性0

2.3.5内存顺序模型0

2.4CPU编程模型0

2.4.1寄存器0

2.4.2指令集0

2.5鲲鹏处理器与毕昇编译器0

2.5.1毕昇编译器的优化特性0

2.5.2FORTRAN语言支持0

2.6小结0

2.7深入阅读0

2.8习题0

第3章编译器前端0

3.1词法分析0

3.1.1记号0

3.1.2正则表达式0

3.1.3有限状态自动机0

3.1.4Thompson算法0

3.1.5子集构造算法0

3.1.6Hopcroft算法0

毕昇编译器原理与实践

目录

3.2语法分析0

3.2.1上下文无关文法0

3.2.2推导0

3.2.3分析树0

3.2.4自顶向下分析0

3.2.5自底向上分析0

3.3语义分析0

3.3.1抽象语法树0

3.3.2符号表0

3.3.3语义检查0

3.4小结0

3.5深入阅读0

3.6习题0

第4章中间表示0

4.1中间表示概述0

4.1.1树状表示0

4.1.2有向无环图0

4.1.3控制流图0

4.1.4依赖图0

4.1.5线性表示0

4.2中间代码生成0

4.2.1算术运算符0

4.2.2布尔运算符和关系运算符0

4.2.3数组的存储和访问0

4.2.4字符串0

4.2.5结构引用0

4.2.6控制流结构0

4.2.7过程调用

4.3静态单赋值形式

4.3.1基本概念

4.3.2SSA形式的构建

4.3.3SSA形式的消去

4.4小结

4.5深入阅读

4.6习题

第5章中端分析与优化

5.1控制流分析

5.1.1控制流分析方法

5.1.2流图的遍历

5.2数据流分析及优化

5.2.1优化的基本结论

5.2.2三地址码中间表示

5.2.3数据流分析

5.2.4程序优化

5.2.5数据流分析的改进

5.3别名分析

5.3.1基于类型的别名分析

5.3.2基于流的别名分析

5.3.3别名信息的使用

5.4过程间分析及优化

5.4.1分析

5.4.2优化

5.5循环优化

5.5.1循环

5.5.2归纳变量

5.5.3数组边界检查

5.5.4循环展开

5.5.5毕昇编译器的其他循环优化

5.6多级存储优化

5.6.1数据预取

5.6.2数据重组

5.7反馈式优化

5.7.1基本块重排优化

5.7.2函数内联优化

5.7.3寄存器溢出策略

5.8小结

5.9深入阅读

5.10习题

第6章后端与优化

6.1指令选择

6.1.1瓦片覆盖

6.1.2最大吞进

6.1.3动态规划

6.1.4执行效率

6.2指令调度

6.2.1指令级并行

6.2.2依赖图

6.2.3局部表调度

6.2.4全局调度

6.2.5软件流水

6.3寄存器分配

6.3.1干涉图

6.3.2图着色

6.3.3Kempe算法

6.3.4溢出

6.3.5接合

6.3.6干涉的保守性

6.4自动向量化

6.4.1概述

6.4.2毕昇编译器中的自动向量化

6.5小结

6.6深入阅读

6.7习题

第7章毕昇编译器AI自动调优

7.1基本原理

7.1.1迭代自动调优

7.1.2预测性自动调优

7.2毕昇自动调优

7.2.1毕昇自动调优的职责和功能

7.2.2安装Autotuner

7.3调优方法

7.3.1准备工作

7.3.2使用方法

7.4小结

7.5深入阅读

第8章毕昇编译器使用

8.1毕昇编译器介绍

8.2毕昇编译器安装使用

8.2.1环境依赖

8.2.2获取毕昇编译器

8.2.3安装毕昇编译器

8.2.4使用毕昇编译器

8.3毕昇编译器选项说明

8.3.1默认选项

8.3.2指定数学库

8.3.3指定jemalloc

8.3.4LTO优化

8.3.5浮点运算控制选项

8.3.6自定义优化选项

8.4FORTRAN 语言引导语

8.5GDB调试

8.5.1约定

8.5.2不支持场景

8.5.3通过升级GDB版本解决部分问题