嵌入式系统可重定向功耗优化编译器研究

摘要

该文对编译器后端的代码选择算法、可重定向代码生成框架以及功耗优化编译器后端实现进行了系统深入的研究.编译器可重定向性实现最重要环节就是代码选择阶段.理想的代码选择算法应可充分利用指令集描述信息,选定最优操作流,同时还应具备结构灵活性和高搜索效率.在深入的分析总结了现有代码选择算法之后,该文提出了针对不同问题的三种代码选择算法,即基于图结构的代码选择算法、解决模板重叠问题的代码选择算法和可支持复杂模板的代码选择算法.分别给出了算法描述、伪码和复杂度分析.该论文提出了一个阶段耦合代码生成框架,其主要思路是将代码选择以及寄存器分配阶段的所有选择空间保留到最后,与调度一同完成.文中详细描述了这种代码生成框架的整体结构、工作流程和实现算法,同时给出了对该框架中的模板匹配以及各种图结构的形式化定义和分析,并从理论上验证了它们的构造算法和搜索算法的正确性.文中提出了一个新的调度完全图搜索方法,并给出了该方法各步骤的详细描述.调度完全图搜索过程包含三大步骤:调度完全图首次搜索、选定操作流分析和二次调度及寄存器分配.为了实际验证该文提出的代码生成框架的有效性,在该框架的基础上实现了一个可重定向功耗优化编译器后端XP_compiler.目前该编译器后端可实现对RISC和VLIW体系结构的重定向.文中具体的描述了该编译器后端的整体结构、1该论文得到国家自然科学基金项目(60273042)、安徽省自然科学基金项目(03042101)以及中国科技大学创办一流大学研究经费的支持.各模块主要数据结构、工作流程以及处理器模型,同时介绍了XP ADL语义及相关数据结构.XP_compiler依据Tiwari提出的指令级功耗模型,将指令的功耗分为单指令基本功耗和前后指令相干功耗,将功耗数据加入XP ADL的指令集描述中,并利用XP ADL驱动了基于功耗的调度完全图启发式搜索算法.文中详细说明了该算法的搜索步骤,给出了算法描述.论文最后利用simplepower模拟器对XP compiler输出的DLX汇编指令进行了仿真,验证了该文所提出的阶段耦合代码生成框架和功耗优化搜索算法的正确性和有效性.同时利用XP compiler输出的VCore汇编指令验证了XP compiler的重定向和代码优化能力.

目录

文摘

英文文摘

致谢

第1章 绪论

1.1 嵌入式系统及其设计技术的发展趋势

1.1.1嵌入式系统的设计约束

1.1.2嵌入式系统设计方法学

1.1.3嵌入式系统低功耗设计技术

1.1.4上市时间TTM与设计环境

1.2嵌入式系统设计环境

1.2.1设计环境框架

1.2.2可重定目标能耗优化编译器

1.2.3编译器结构

1.2.4体系结构描述语言ADL

1.3与本论文相关的研究工作概述

1.3.1 Aviv

1.3.2 SUIF

1.3.3 RECORD

1.3.4 TRIMARAN

1.3.5 SPAM

1.3.6 GCC

1.3.7 Zephyr

1.3.8研究成果的比较与存在问题

1.4本论文工作

1.4.1研究目标

1.4.2本论文所做工作

1.4.3本论文的组织

第2章 编译器结构与设计技术

2.1编译器组成与工作流程

2.2编译器相关概念

2.3编译器优化方法

2.4典型可重定向编译器分析

2.4.1 GCC

2.4.2 TRIMARAN

2.5 可重定向优化编译器的设计要求

2.6体系结构描述语言XP_ ADL

2.6.1 XP_ ADL功能

2.6.2 XP_ ADL语义

2.6.3 XP_ ADL语法

2.6.4体系结构行为描述

2.6.5体系结构微结构描述

2.7小结

第3章 代码选择算法研究

3.1代码选择研究发展状况

3.1.1 Twig提出的树模式匹配算法

3.1.2 Burg树匹配算法

3.1.3 BEG

3.1.4 M.Anton Ertl的图结构中间代码的代码选择算法

3.1.5已有代码选择算法的缺陷

3.2一种基于图结构的代码选择算法

3.2.1算法描述

3.2.2伪码描述

3.2.3复杂度分析

3.2.4例证

3.3 一种解决模板重叠问题的代码选择算法

3.3.1模板重叠问题

3.3.2算法描述

3.3.3伪码描述

3.3.4例证

3.4支持复杂模板的代码选择算法

3.4.1复杂指令描述

3.4.2复杂指令划分

3.4.3子模板规约规则

3.4.4复杂指令代码选择算法描述

3.4.5伪码描述

3.4.6例证

3.5 小结

第4章 可重定向代码生成框架研究

4.1 已 有可重定向编译器后端研究缺陷

4.2编译后端的阶段耦合技术

4.2.1集成的寄存器分配和指令调度

4.2.2将代码选择和寄存器分配集成到调度中

4.2.3集成的代码选择、寄存器分配和调度三阶段

4.3 一种三阶段耦合代码生成框架PCGF

4.3.1阶段耦合的理由

4.3.2阶段耦合框架PCGF描述

4.3.3 DFG生成

4.3.4 DFG标记

4.3.5 CSCG生成

4.3.6 SCG生成

4.3.7 SCG启发式搜索

4.3.8汇编码生成

4.4阶段耦合框架PCGF的形式化验证

4.4.1中间代码和DFG图的形式化验证

4.4.2模板的描述和匹配的形式化证明

4.4.3 CSCG图的形式化证明

4.4.4 SCT树的形式化证明

4.4.5 SCG图的形式化证明

4.5 阶段耦合代码生成框架的性能分析

4.6小结

第5章 基于阶段耦合的能耗优化编译器后端设计与实现

5.1DLX体系结构

5.1.1 DLX基本结构

5.1.2 DLX流水线结构

5.2 VCore体系结构

5.2.1操作编码格式

5.2.2操作定义

5.2.3流水线

5.3体系结构建模

5.3.1指令集

5.3.2流水线结构

5.3.3内存结构

5.3.4资源描述

5.4模块划分

5.4.1 DFG生成模块

5.4.2 XP-ADL处理模块

5.4.3代码选择完全图CSCG生成模块

5.4.4调度完全图SCG生成模块

5.4.5汇编代码生成模块

5.5调度完全图启发式搜索

5.5.1多发射体系结构的调度完全图搜索

5.5.2单发射体系结构的调度完全图搜索

5.6针对功耗优化的代码生成

5.6.1指令级功耗模型

5.6.2 XP_ ADL中功耗模型描述

5.6.3针对功耗优化的调度完全图启发式搜索算法

5.7小结

第6章XP_compiler实验测试环境及结果

6.1 定向到DLX体系结构的测试

6.1.1实验测试方案

6.1.2 Simplepower简介

6.1.3 DLX指令集功耗数据

6.1.4 Simplepower测试数据

6.1.5测试结果分析

6.2定向到VCore体系结构的测试

6.2.1实验测试方案

6.2.2实例分析

6.2.3实验数据

6.3 DSP复杂指令测试

6.4小结

第7章总结

7.1论文所做的主要工作

7.2论文的新贡献

7.3未来工作展望

参考文献

攻读博士学位期间发表的有关论文