Survey on Java Pointer Analysis
-
摘要:
近年来静态程序分析已成为保障软件可靠性、安全性和高效性的关键技术之一. 指针分析作为基础程序分析技术为静态程序分析提供关于程序的一系列基础信息，例如程序任意变量的指向关系、变量间的别名关系、程序调用图、堆对象的可达性等. 介绍了Java指针分析的重要内容：指针分析算法、上下文敏感、堆对象抽象、复杂语言特性处理、非全程序指针分析，特别是对近年来指针分析的研究热点选择性上下文敏感技术进行了梳理和讨论.
Abstract:In recent years, static program analysis has become one of the key techniques to ensure the reliability, security and efficiency of software. As a fundamental program analysis technique, pointer analysis provides a series of fundamental information about the program for static program analysis, such as the points-to relations of any variables in the program, alias relations between variables, program call graph, and the reachability of heap objects. We introduce the important contents of Java pointer analysis, including pointer analysis algorithm, context sensitivity, abstraction of heap objects, handling of complex language features, non-whole program pointer analysis, especially we sort-out and discuss selective context sensitivity, which is the research hotspot of pointer analysis in recent years.
-
Keywords:
- pointer analysis /
- alias analysis /
- Java /
- static analysis /
- context sensitivity
-
处理器芯片已经成为现代信息社会的基石，是推动新一轮科技革命和产业变革的关键力量[1]，对于提升国家战略竞争力和国际地位具有重要意义[2]. 作为计算机系统的核心和大脑，处理器负责执行各类控制、计算任务，其性能和功耗等设计指标对整个系统至关重要. 因此，处理器的设计制造在集成电路和计算机产业中占据了关键地位.
随着半导体工艺的发展，晶体管特征尺寸逐步逼近物理极限，摩尔定律所预测的等比例微缩定律已经难以维持，给处理器的设计制造带来了诸多挑战. 随着平面光刻衍射极限[3]、短沟道效应[4]、冯·诺依曼瓶颈[5]等问题愈发突出，现代处理器面临尺寸缩小瓶颈、能耗瓶颈和算力瓶颈等问题. 当特征尺寸进入量子效应显著的范围，诸多次级物理效应随之显现，比如源漏寄生电阻占比增大、栅极隧穿泄漏等，导致芯片的功耗密度快速上升，散热问题也限制了处理器的主频提升，集成电路已经进入功耗限制时代[2].
传统的超大规模集成（very large scale integration，VLSI）电路基于分阶段设计的思想，层层分解，在各个阶段进行局部最优化设计，有利于缩减问题规模、提高设计效率. 然而，随着处理器规模的急剧攀升，传统设计流程愈发难以收敛于全局能效最优. 各阶段的相对独立导致了设计鸿沟的产生，难以支撑跨层次联合设计，无法达到架构、电路、器件跨层优化的性能水平[2]. 因此，必须采取不同设计阶段和设计模式相协同的思想，考虑不同阶段的相互影响，实现跨层优化，使得最终结果收敛于全局最优，并减少设计迭代. 研究人员已经尝试从全系统的角度进行设计，并利用机器学习（machine learning，ML）[6]强大的建模和优化能力打破设计壁垒. 左移融合的新型设计范式[7]也对设计工具提出了更高的挑战，研发更加智能高效的新一代电子设计自动化（electronic design automation，EDA）工具势在必行.
对于商业处理器而言，能否在完成既定设计指标的前提下，尽可能缩减物料和开发成本成为产品竞争力的重要考量. 因此，在早期架构设计阶段前瞻性地评估性能、功耗、面积（performance, power, and area，PPA）等指标，并探索符合需求的微架构设计显得尤为重要. 一般而言，微架构设计方案形成设计文档，并通过工程开发的方式转换为寄存器传输级（register transfer level，RTL）代码，然后利用EDA工具完成逻辑综合和物理版图设计. 微架构设计所描述的每一个简单语句都可以很轻易地转换为成千上万行 RTL 代码，导致设计复杂度急剧攀升、问题规模爆炸性增长. 因此，如何在早期微架构设计阶段较为精确地预估PPA指标，并对不同设计方案进行探索和优化，对于提高开发效率至关重要.
目前，手机、汽车电子、AIoT等各类设备发展迅猛，迫切需要定制化、高能效的处理器设计，以及系统性的芯片敏捷设计方案[8]. 作为开发流程中极为关键的一步，微架构建模和探索优化的质量和效率决定了能否快速获得理想的处理器芯片，直接影响开发周期和投入产出. 本文将介绍微架构功耗建模和设计空间探索领域的研究进展，尤其是如何利用机器学习技术提高建模、优化过程中的性能和效率.
1. 背景介绍
1.1 处理器设计流程
VLSI的设计制造是一个复杂庞大的工程，为了应对不断发展的芯片集成度和半导体工艺，其设计流程也日趋多样化. 目前，层次化设计是被采用最多的设计方法.
图1给出了处理器芯片的典型设计流程. 系统定义[9]主要根据客户需求定义产品的基本结构、目标和原则，确定系统功能、PPA以及工艺选择等. 架构设计[10]则给出目标处理器的基本架构，包括模拟和混合数字模块的集成、软硬 IP 核的使用、内存管理、通信、电源要求等. 其中，微架构用于实现给定的指令集架构（instruction set architecture，ISA），包括该实现的特定机制和硬件结构，并在一定约束条件下使用硬件电路结构进行描述. 功能和逻辑设计[11]则定义了目标设计的功能行为，并通过高层次硬件模型实现，比如使用Verilog/VHDL等高级硬件描述语言完成RTL代码开发. 在给定工艺库后，逻辑综合[12]将RTL代码转换为门级网表，并完成逻辑化简和优化. 在获得门级网表后，基于工艺库信息进行布图规划、布局、布线等后端物理设计[13]步骤，从而将电路元器件和互连关系映射到晶片上. 然后，对物理版图进行物理验证、测试等各项检查验证. 如果满足既定PPA设计指标，则通过签核形成标准版图文件交付半导体制造商，并经过一系列工艺制造、封装测试形成最终产品交付客户. 而如果不满足既定设计目标，则需要修改早期设计，并重新执行后续设计流程.
为了获得更加理想的设计结果，处理器开发往往需要大量的反馈迭代，导致开发周期长、全局优化不足、设计成本大幅度增加. 因此，为了避免复杂耗时的后期设计和验证流程，有必要在早期设计阶段从全系统的角度进行跨层优化，并开发更加高效智能的EDA工具. 总而言之，在早期的微架构设计空间中进行精确高效的建模和优化，有利于为处理器设计实现良好开端，从而缩短设计周期、降低开发成本.
1.2 微架构设计及其面临的挑战
在计算机系统中，微架构是处理器对特定ISA的实现，也称为微体系结构. 这种实现通常是指寄存器、存储器、控制器、算术逻辑单元和其它数字逻辑块的组合实现. 换而言之，微架构给出处理器中存在的所有电子元件和数据路径的逻辑设计，并以特定方式布局，从而实现指令的最佳执行. 微架构与 ISA 相结合组成了整个系统的计算机体系结构，设计人员可以使用不同的微架构设计来实现一个给定的 ISA，从而解决不同的问题，比如加速某种特定任务、降低功耗、提高成本效益等. 如图1所示，微架构设计处于整个设计流程的上游，对处理器芯片的PPA有关键影响，因此往往需要在多个维度进行权衡.
作为处理器设计方式的逻辑表示，通常将特定的微架构表示为数据流图，用以描述各种组件的互连和交互. 作为示例，图2给出了RISC-V BOOM处理器的微架构示意图. RISC-V是一种开源 ISA，因其免费、简洁以及良好的可移植性等特点，受到了广泛关注和支持，并取得了显著发展[14-18]. BOOM[14-15]通过使用Chisel[19]来构建内核生成器，能够提供一系列乱序RISC-V内核设计，以适应不同的应用场景. 如图2所示，BOOM主要由前端（FrontEnd）、指令解码单元（IDU）、执行单元（EU）和加载存储单元（LSU）4个部分组成. 得益于BOOM的可参数化微架构设计，设计人员可以通过配置不同的微架构设计参数，在性能和功耗等指标之间做出不同的权衡. 由于对开发人员友好、性能高、可配置等优点，BOOM 在开源社区备受追捧. 同时，BOOM为微架构建模和探索优化提供了很好的机会，本文所调研的很多工作都是基于BOOM展开的.
分支预测等各级流水线设计，执行单元的数量、延迟、吞吐量选择，存储器的大小、延迟、吞吐量和连接性等均是微架构设计和决策的核心任务. 随着设计需求的日益复杂和制造工艺的不断发展，设计人员必须最大程度地压缩开发周期，以加快上市时间. 重要的是，必须考虑能效、成本和可扩展性等诸多因素，对流水线和各个组件进行细致地分析和评估，以尽早评估目标设计的PPA指标，从而确定最适合特定应用场景的微架构设计方案，以提高处理器的性能和能源效率. 然而，互相冲突的设计指标、漫长耗时的开发流程、复杂庞大的设计空间，给微架构建模和探索决策带来了3个严峻的挑战：
1）处理器芯片所关注的设计指标，例如性能和功耗是负相关的，甚至是相互冲突的，无法实现全部指标的同时最优，必须考虑如何做出良好权衡.
2）传统的设计验证流程极为耗时，对给定微架构设计方案进行PPA评估通常需要花费大量时间，如何利用有限的早期特征信息进行较为精确的PPA预估成为挑战.
3）现代处理器包含许多复杂的组件，并由此产生了极为庞大的设计空间，几乎不可能遍历每种微架构设计以获得最佳解决方案，如何高效探索全局最优设计成为挑战.
1.3 机器学习辅助集成电路设计
为了解决集成电路设计领域面临的诸多挑战，研究人员尝试应用机器学习等人工智能（artificial intelligence，AI）[20]技术赋能芯片设计. 人工智能的概念于1956年首次被提出，并在棋类游戏、计算机视觉、自然语言处理等应用中取得了重大突破，是未来科技发展的重要方向. 机器学习使用计算机模拟人的学习行为，并从数据中学习知识以改进预测模型和智能系统的性能. EDA 应用中的很多问题可以表征为决策问题、回归问题与检测问题，具有多阶段、多目标、不连续、非线性等特点，且面临较大的不确定性和时间压力. 通过应用机器学习技术，可以有效利用历史数据和知识来构建更加准确的电子设计模型、开发处理器的跨层优化方法，提高EDA工具的自动化和智能化程度，从而帮助设计人员快速生成高质量的芯片设计.
目前，机器学习在EDA领域的应用仍处于探索阶段，但已经取得了一些显著进展. Cadence发布了基于机器学习引擎的数字全流程，芯片设计吞吐量最高提升 3 倍，PPA最多改善 20%. Synopsys则推出了AI自主芯片设计系统 DSO.aiTM，利用强化学习在芯片设计的庞大解空间中搜索优化目标，在降低设计成本的同时获得PPA提升. Mentor（现西门子EDA）推出了用于更智能设计的AI/ML工具包，其中AI辅助的高层次综合（high level synthesis，HLS）工具能够快速找到神经网络加速器引擎的最佳 PPA 实现，基于机器学习的光学邻近校正工具和光刻仿真工具能在保持最佳精度的同时大幅度提高设计效率. 得益于数十年的积累，EDA厂商拥有丰富的全流程工具和流片验证经验，为利用机器学习技术辅助EDA工具开发提供了充足的数据和实践积累.
学术界也对机器学习技术在 EDA 领域的应用开展了大量研究. 如图3所示，Rapp等人[21]总结了2016−2020年间在五大主要EDA学术期刊和会议中，使用机器学习进行集成电路辅助设计的出版物数量及其在不同阶段的占比. 从图3（a）不难看出，使用机器学习解决 EDA 问题正变得越来越流行. 如图3（b）所示，在2020年，约有65%的工作是用于物理设计和制造阶段的，因为这些工作涉及物理版图的几何表示，有利于应用较为成熟的图像相关的机器学习算法. 而在早期设计阶段，如系统级设计空间探索（design space exploration，DSE）、HLS、逻辑综合等相关研究则较少. 这些问题大多是组合优化问题，在理论上更加难以求解，且缺乏领域知识的引入和可扩展性研究. 根据上述统计，机器学习用于后端物理设计和制造阶段已被广泛研究，未来需要把更多的精力集中于较早期的设计阶段，这也是本文的重点所在.
![]()
总的来说，机器学习与EDA方法学的融合是革命性的一步，使得芯片设计生产力产生质的飞跃. 首先，机器学习强大的建模能力能够为设计流程中较早期阶段提供精准高效的指标评估，有利于实现跨层优化. 其次，数据驱动的机器学习模型能够为特定流程和场景提供定制化算法、减少人工干预，具备更高的自动化和智能程度. 此外，通过将复杂的EDA问题转化为机器学习问题，能够有效降低EDA算法开发门槛，吸引更多研究人员.
2. 微架构功耗建模
集成电路的功耗建模是一个广泛而持久的研究问题. 随着摩尔定律的放缓和登纳德缩放定律的崩溃，功耗问题已经成为高能效处理器设计的主要挑战，集成电路已经进入功耗限制时代[2]. 因此，迫切需要开发精确鲁棒的功耗模型以指导处理器芯片的设计和优化. 研究人员已经针对不同设计阶段提出了一系列建模方法. 然而，现代处理器架构复杂、设计空间庞大，现有模型依然难以满足不断增长的建模速度、通用性和准确性需求. 本节将介绍功耗建模问题、相关建模方法，重点在于机器学习辅助微架构功耗建模，并进行小结.
2.1 功耗建模问题
作为处理器芯片开发中的主要挑战与优化目标，需要在设计阶段尽早地对功耗进行建模和估计，以便对不同设计方案进行探索决策. 在这种情况下，功耗模型需要具备对不同硬件设计，以及所运行的不同工作负载进行精确建模的能力，并助力设计空间探索和优化.
功耗通常指集成电路在单位时间内所消耗的能量，即所需的电源功率. 一般而言，集成电路的总功耗P包含3个主要部分：开关功耗（switching power）、短路功耗（short circuit power）和漏电功耗（leakage power），由式（1）给出：
P=αCV2ddfclk+αESfclk+VddIleak. (1) 式（1）中第1项为开关功耗，是指电路单元在驱动外部电容性负载切换状态时进行充放电所消耗的能量/功率，也称为翻转功耗或者狭义的动态功耗. 开关功耗与总负载电容（C）、电源电压（Vdd）、时钟频率（fclk）和活动因子（α）成正比，其中α通常为每个周期的平均开关次数.
式（1）中第2项为短路功耗，是指电路切换期间PMOS管和NMOS管同时打开形成的短路电流以及单元内部电容充放电所引起的内部功耗（internal power），内部能量通常以脉冲形式耗散. ES为每个开关操作的短路能量、fclk 为时钟频率，α为活动因子.
式（1）中第3项为漏电功耗. 晶体管实际上只能充当“不完美”开关，当未发生状态切换时，通过晶体管的漏电流仍然会产生漏电功耗. 漏电功耗取决于漏电流（Ileak）和电源电压（Vdd）. 漏电流主要包括晶体管沟道和栅极之间的栅极漏电流，漏极和源极之间的亚阈值漏电流，以及漏极和衬底之间的反向偏置电流. 随着晶体管特征尺寸和氧化物厚度的缩小，漏电功耗愈发不可忽视.
开关功耗和短路功耗均是电路开关活动导致的，可将两项之和称为广义的动态功耗（dynamic power）；而漏电功耗与电路活动无关，不依赖于开关切换，相对保持恒定，也可称之为静态功耗（static power）. 通常而言，在数字电路中，动态功耗为总功耗的主要来源，但随着特征尺寸的持续缩小，漏电流所导致的漏电功耗持续增长，并导致了登纳德缩放定律的崩溃，成为了先进制程发展中的极大阻碍.
2.2 相关功耗建模方法
在传统设计流程中，作为黄金标准的功耗估计通常是由门级商业分析工具，例如 PrimeTime PX（PTPX）[22]完成的，这需要以长时间的门级设计及仿真为代价，并且只能在设计流程的较晚阶段使用，难以辅助处理器芯片的跨层优化.
为了避免门级功耗分析的高昂成本，研究人员尝试在更高的抽象层次（即更早的设计阶段）进行功耗建模. 一般而言，越在后期设计阶段进行的功耗建模会越精确，但相应的建模成本也会大幅度提高. 图4对用于不同抽象层次的功耗建模工作进行了统计，根据是否需要 RTL 实现和仿真，可以将现有功耗建模方法分为：微架构级和RTL/门级. 一般而言，门级商业分析工具给出的估计结果被认为是黄金标准值，其他门级功耗模型的误差在1%~5%；RTL级模型通常依赖于仿真波形信号，能够实现较为精确的细粒度功耗估计，误差范围为1%~10%；而微架构级模型通常只能利用架构级的有限信息对不同粒度的平均功耗进行估计，误差范围为2%~20%.
2.2.1 微架构功耗建模
在整个设计流程中，微架构级别的功耗建模和优化有难以替代的优势，这是因为系统级别的功耗优化技术往往能够实现较高的节能收益. 文献[23]的研究显示，电源关断（power shut off，PSO）技术可以实现约95%的漏电功耗优化，动态电压频率调节（dynamic voltage and frequency scaling，DVFS）可以带来30%~60%的动态功耗节省，多电压域（multiple supply voltage, MSV）架构则可以带来约40%的功耗优化. 在主流的设计流程，如UPF（unified power format）设计流程，首先需要在微架构阶段进行定义，并由综合工具完成低功耗单元（如isolation cells，level shifter cells）的实现，且要求在后端设计中使用特殊的电源管理库文件（PMK Kits）. 显然，快速精确的微架构功耗模型成为开发系统级功耗优化技术的关键前提，使其成为十分典型且亟需解决的跨层优化问题.
在微架构层面，功耗模型通常只能基于有限的微架构设计参数和性能仿真信息等来对不同时间粒度的平均功耗进行建模. 由于无需RTL开发和仿真，微架构级的功耗建模通常具有极快的建模速度，以及较高的通用性和可扩展性，但由于难以获得详细的后端电路实现细节，导致建模精度较低.
最为普遍使用的是各类架构级解析功耗模型[24-26]，它们试图建立不同的硬件表示和库函数，并使用来自性能模拟器[27-30]的事件统计信息获得最终的功耗估计. Wattch[24]根据微架构组件的电容模型和架构模拟获得的开关事件计算动态功耗. CACTI[25]使用ITRS器件模型和MASTAR[31]获得不同工艺节点下的器件参数，重点支持基于SRAM和DRAM的缓存和内存阵列. PowerTimer[32]使用一组参数化的能量函数对微架构性能模拟中的分层组件进行功耗建模. Orion[33]是一种用于估计片上网络功耗的工具，使用重复布线模型进行互连，并使用 MASTAR 和其它方法根据 ITRS 获得器件参数. McPAT[26]基于 ITRS 预测的 CMOS 器件参数，支持 90~22 nm 节点下多核处理器的功耗、面积和时序建模，提供了从架构级别到工艺级别的完整层次式模型. McPAT 具备高度的灵活性和可扩展性，被广泛应用于处理器架构设计，但由于其内部模型与实际设计之间的错位，其建模误差高达20%∼40%[34-35]，且缺乏对先进工艺节点的支持. McPAT-PVT[36]和McPAT-Monolithic[37]分别将 McPAT 扩展到20 nm和14 nm FinFET 工艺节点，但并没有完全解决精度不足的问题. Ravipati等人[38]提出了FN-McPAT，集成了FinFET工艺下BOOM 内核的综合结果，以支持14 nm FinFET及NC-FinFET（负电容鳍式场效应晶体管）工艺. Van den Steen等人[39]提出了独立于微架构的机理模型完成处理器的功耗建模，从而加速大规模设计空间探索. Park等人[40]在更高的指令级别下进行建模，用于创建多个粒度级别的处理器功耗模型，从而快速映射到电子系统设计流程.
2.2.2 RTL/门级功耗建模
RTL/门级功耗模型需要进行 RTL 或门级网表设计和仿真，其通常是基于仿真所得的波形信号所建立的. 在 RTL 层次，PowerArtist[41]和PowerPro[42]等行业工具可以提供粗粒度的RTL总功率估计. Bogliolo等人[43]使用基于回归的方法支持以更小的粒度构建功耗模型，但以有限的精度为代价. PrEsto[44]使用线性模型通过FPGA加速来描述不同的电路模块. Yang等人[45]使用基于奇异值分解的特征选择技术来构建线性功耗模型. PRIMAL[46]使用卷积神经网络来处理寄存器切换活动，为可重复使用的电路构件的功耗进行建模. Simmani[47]使用VCD dump来构建一个切换模式矩阵，并通过聚类选择关键信号来构建功耗模型，能够提供更高精度的 RTL 功耗估计. GRANNITE[48]将门级网表转换为图，并将 RTL 仿真中的寄存器状态和单元输入作为特征来构建图形神经网络模型，以预测门的切换率和平均功耗. APOLLO[49]使用基于MCP（minimax concave penalty）正则的线性回归实现特征选择，从而使用少量 RTL 信号来完成逐周期的功耗建模，以用作设计时功耗估计器和运行时片上功耗监控器. Fang等人[50]提出了一种用于RTL设计的综合前PPA估计框架MasterRTL，首先将HDL代码转换为简单运算符图的bit级表示形式，在时序建模中捕获详细关键路径信息，并在功耗建模中集成切换率和模块级信息，从而实现对布局后PPA 值的精确预测.
RTL/门级功耗模型依赖于更详细的硬件细节和仿真波形，能够实现相对较高的建模精度，甚至能够实现逐周期的精确建模. 尽管如此，2个关键缺点导致这些模型难以应用于早期的微架构设计阶段：1）详细的逻辑设计和仿真需要投入高昂的人力和时间成本，且速度较慢，在早期微架构设计阶段难以使用；2）由于不同设计的硬件网表和仿真波形差别较大，导致所得的功耗模型大多是特定于硬件设计的，在不同的处理器设计间进行迁移面临挑战.
2.3 机器学习辅助微架构功耗建模
随着AI领域的飞速发展，机器学习模型的强大建模能力为早期阶段的精确指标评估提供了可能. 截止目前，研究人员已经开发出基于各类统计学习或机器学习的建模方法，实现了更加精确的微架构功耗模型，为处理器芯片的跨层优化提供了有效工具.
早期工作[51]使用微架构设计参数进行统计回归建模来辅助设计空间探索，但由于缺乏与工作负载相关的事件统计等信息，难以准确地对不同的工作负载程序进行建模.
基于微架构仿真事件的设计时功耗模型[52]和基于性能监视计数器（performance monitoring counter，PMC）的运行时功耗模型[53-55]则被更加广泛地使用. Jacobson等人[52]使用相对较少的程序事件来进行功耗建模. Bircher等人[53]利用了处理器性能事件的“涓滴效应”，进而确定了6个PMC事件对整个系统功耗进行回归建模. Walker等人[54]建立了一个运行时功耗模型，并通过自动选择最佳的PMC事件来实现静态功耗和动态功耗的分离. Sagi等人[55]使用非线性变换来捕捉 PMC 事件和功耗值之间的关系，并使用最小角度回归来完成多变量的多项式功耗回归建模. Lebeane等人[56]提出了WattWatcher，通过将性能事件计数和硬件描述文件传递到基于McPAT的可配置后端模型中，从而进行运行时功耗监控. 如图5所示，Reddy等人[57]将基于PMC的运行时经验模型[53]转化为设计时微架构功耗模型，并与gem5模拟器[29]相结合，从而实现了用于早期阶段的设计时功耗建模. 然而，机器活动所产生的事件信息通常与具体硬件配置密切相关，导致这些功耗模型多是特定于硬件设计的，难以对新型目标处理器做出良好预测.
Ipek 等人[58-59]利用人工神经网络（artificial neural network，ANN）来捕获架构参数和性能/功耗之间的关系，以此构建准确的预测模型促进设计空间探索. 此外，为了减少所需采样架构的数量以构建满足特定精度约束的预测模型，使用智能采样来实现高效的训练过程. 他们在内存系统、处理器、芯片级多核处理器上验证了其方法的有效性.
如图6所示，Kumar等人[60]从周期精确的微架构仿真中获得高级活动信号，例如每个模块的数据信号、控制信号、混合信号，并基于不同输入信号执行特征选择和特征工程，然后使用非线性回归模型对不同微架构模块构建功耗模型，从而形成分层组合的完整处理器功耗模型. 在实验中，他们使用Verilator工具[61]从处理器的 RTL 描述生成周期精确的 C++模型，并在有序执行的RI5CY处理器[62]和乱序执行的BOOM处理器上进行了验证.
由于其易用性和就绪性，解析功耗模型McPAT受到了广泛欢迎，但其建模误差愈发难以接受. 如图7所示，为了提高建模精度，PowerTrain[35]基于来自真实硬件的功耗测量结果，使用带有L1正则的线性回归来重新加权McPAT 中每个组件的估计功耗，从而提供更加精确的运行时功耗估计.
Zhai等人[63-64]提出了一种将解析建模与机器学习校准相结合的微架构功耗建模框架McPAT-Calib，其建模流程如图8所示. 首先对经典解析模型McPAT进行底层改进，然后确定了包含微架构设计参数、活动统计信息、解析功耗建模结果在内的广泛建模特征，并使用自动特征选择和非线性回归等机器学习方法做进一步校准，还设计了一种主动学习采样方法PowerGS来降低机器学习模型对标记数据规模的需求，从而以较低代价实现建模精度和通用性的提升. Zhai等人使用BOOM处理器的15种微架构配置和80种负载程序进行了验证.
Zhang等人[65]得出了统一现有架构级功耗模型的通用公式及PANDA框架. 如图9所示，PANDA框架结合了解析模型和机器学习模型的优点，在训练数据有限的情况下准确地预测功耗、面积、性能，该框架不依赖于特定解析功耗模型，并支持对未知新工艺节点的预测. PANDA框架中，每个组件的PPA预测模型由2个子模型组成，其中非斜线部分表示解析性的资源函数模型，斜线部分则表示机器学习模型. 该框架也在BOOM处理器上进行了验证.
如图10所示，为了提高基于机器学习的微架构功耗模型的可迁移性，Zhai等人[66]提出了一种基于神经网络和迁移学习的微架构功耗建模方法. 首先，根据先验知识设计基于ANN的微架构功耗模型，然后使用跨域混合生成接近于目标分布的辅助样本，并利用改进的域对抗训练完成知识迁移和模型构建. 在BOOM处理器不同微架构配置上的迁移实验证明了该方法的有效性.
![]()
Wang等人[67]探索了跨工作负载的可迁移性，提出了一种迁移学习设计空间探索框架TrEnDSE来执行跨工作负载的性能预测. 首先，利用Wasserstein距离量化工作负载之间的黑盒可迁移性，并作为初始样本权重，设计了可迁移性感知的迁移学习算法自适应调整样本权重；此外，使用了集成装袋（bagging）学习模型和不确定性驱动的迭代优化方法，以利用这些样本权重来执行准确且鲁棒的性能和功耗预测.
如图11所示，Li等人[68]提出了一种基于图神经网络的PPA估计框架NoCeption，用于具有任意不规则拓扑和可变设计参数的片上网络（network on chips，NoC）的快速预测. 他们采用一种通用表示方法将NoC和应用任务图转换为属性图，并使用消息传递神经网络（message passing neural network， MPNN）转换为有效的图嵌入特征，从而实现NoC的PPA预测.
2.4 小 结
总的来说，在微架构设计阶段前瞻性地进行功耗估计有利于实现跨层优化、提升设计质量和效率. 然而，由于处在较高的抽象层次，微架构设计阶段难以捕获详细的硬件细节，给功耗建模带来了极大挑战. 为了导出数学上可用的预测模型，解析性功耗模型通常需要做出很多假设，且往往与特定的处理器架构高度耦合，导致通用性较差、建模精度较低，限制了解析模型的应用. 在这种情况下，各类机器学习模型被广泛应用微架构阶段的功耗及其他指标估计. 一般而言，基于机器学习的建模方法具有更好的特征提取和函数拟合能力，能够更好地捕捉复杂非线性关系，在估计精度上有可观的提升.
表1从使用阶段、适用范围、建模特征、建模方法及模型误差等方面总结了机器学习辅助的微架构功耗建模方法. 通过分析可以给出常见的功耗建模流程，大致包含4个步骤，即数据采集、特征选择、模型构建和功耗估计. 如何采集合适的训练数据、选择最佳的建模特征，并设计精确鲁棒的功耗模型是上述工作的重点，如图12所示.
表 1 机器学习辅助的微架构功耗建模方法总结Table 1. A Summary of Machine Learning-Assisted Methods for Microarchitecture Power Modeling模型/文献 使用阶段 适用范围 建模特征 建模方法 模型误差 PowerTrain[35] 运行时 不同微架构、不同负载 PMC+硬件描述 线性回归 约2% WattWatcher[56] 运行时 不同微架构、不同负载 PMC+硬件描述 线性回归 平均2.67% 文献[53] 运行时 单一微架构、不同负载 PMC 线性回归 <9% 文献[54] 运行时 单一微架构、不同负载 PMC 线性回归 2.8%~3.8% 文献[55] 运行时 单一微架构、不同负载 PMC 非线性回归 平均6.8% 文献[51] 设计时 不同微架构 微架构设计参数 非线性回归 中位5.4% 文献[52] 设计时 单一微架构、不同负载 仿真活动统计 线性回归 约2.5% 文献[57] 设计时 单一微架构、不同负载 仿真活动统计 线性回归 平均5.9% 文献[58−59] 设计时 不同微架构 微架构设计参数 神经网络 <2% 文献[60] 设计时 单一微架构、不同负载 外部输入信号 机器学习模型 约3.6% McPAT-Calib[63−64] 设计时 不同微架构、不同负载 架构参数、活动统计 解析模型+机器学习 3%~6% PANDA[65] 设计时 不同微架构、不同负载 架构参数、活动统计 解析函数+机器学习 2%~8% 文献[66] 设计时 不同微架构、不同负载 架构参数、活动统计 神经网络+迁移学习 平均4.4% TrEnDSE[67] 设计时 不同微架构、跨负载 架构参数 集成模型+迁移学习 <1% NoCeption[68] 设计时 不同NoC配置及拓扑 架构参数 图神经网络 约2.5% 未来，除了进一步提高功耗模型的建模精度、速度外，在数据获取、模型可迁移性、可解释性等方面仍需要进一步研究. 同时，机器学习模型的训练、推理成本不应抵消在设计早期进行功耗估计的速度优势，因此需要开发低复杂度、高精度、低成本的专用学习模型.
3. 微架构设计空间探索
VLSI的设计总是面临着诸多挑战，因为必须满足一系列严格且相互冲突的设计目标. 设计空间探索已经成为计算机系统设计过程中的基本问题之一[69]. 例如，集成电路的进步显著增加了处理器的复杂性，并产生了大量需要决定的设计参数，例如缓存大小、重排序缓冲区大小等，设计人员需要对不同的微架构设计方案进行探索和比较，从而确保最终处理器能够满足各项设计需求. 本节将介绍设计空间探索问题、相关探索方法，重点在于机器学习辅助微架构设计空间探索并进行小结.
3.1 设计空间探索问题
处理器芯片开发通常需要同时考虑多个优化目标，包括性能、功耗、成本等. 由于设计目标通常是冲突的，因此不可能存在一个同时优化所有目标的最优解决方案. 以图2所示的BOOM处理器为例，经过微架构设计参数的抽取、合法化以及简化后，可形成如表2所示的微架构设计空间，其规模超过108. 显然，在如此庞大的设计空间内探索最优设计面临极大挑战.
表 2 BOOM的微架构设计空间Table 2. Microarchitecture Design Space of BOOM模块 组件参数 描述 备选值 前端 FetchWidth 一次性可取回指令数 4,8 FetchBufferEntry 取指缓冲条目数 8,16,24,32,35,40 RasEntry 返回地址堆栈条目数 16,24,32 BranchCount 同时推测分支数 8,12,16,20 ICacheWay ICache组相连数 2,4,8 ICacheTLB ICache地址翻译缓冲路 8,16,32 ICacheFetchBytes ICache行容量 2,4 指令解码单元 DecodeWidth 一次性最多解码指令数 1,2,3,4,5 RobEntry 重排序缓冲条目数 32,64,96,128,130 IntPhyRegister 整型寄存器数 48,64,80,96,112 FpPhyRegister 浮点型寄存器数 48,64,80,96,112 执行单元 MemIssueWidth 存储型指令发射宽度 1,2 IntIssueWidth 整型指令发射宽度 1,2,3,4,5 FpIssueWidth 浮点型指令发射宽度 1,2 加载存储单元 LDQEntry 加载缓冲条目 8,16,24,32 STQEntry 存储缓冲条目 8,16,24,32 DCacheWay D-Cache 组相联数 2,4,8 DCacheMSHR 缺失状态处理寄存器数 2,4,8 DCacheTLB DCache地址翻译缓冲路 8,16,32 设计空间探索通常可以形式化为一个带约束的多目标优化问题. 给定一组m个决策变量，即探索自由度，适应度函数须优化n个目标值，其定义为：
fi:Rm→R1， (2) 其中，适应度函数fi将解空间X中的点转换为第i个目标值，比如性能、功耗，潜在解{\boldsymbol{x}} \in {R^m}是m个决策变量的赋值. 适应度函数的组合f(x)可以将解空X中的一个点映射到目标空间Y中. 在满足k个设计约束的前提下，使用n个适应度函数fi来确定m个决策变量的解x，以最小化n个优化目标值，即：
\begin{array}{*{20}{c}} {\mathop {\min }\limits_{\boldsymbol{x}} {\text{ }}{\boldsymbol{y}} = f({\boldsymbol{x}}) = ({f_1}({\boldsymbol{x}}),{f_2}({\boldsymbol{x}}),\cdots ,{f_n}({\boldsymbol{x}}))}, \\ {{\rm{s.t.}}{\text{ }}{g_i}({\boldsymbol{x}}) \geqslant 0,i \in [1,{k_1}]}, \\ {{\text{ }}{h_j}({\boldsymbol{x}}) = 0,j \in [1,{k_2}]} , \end{array} (3) 其中 \boldsymbol{x}=(x_1,x_2,\cdots,x_m)\in X ， \boldsymbol{y}=(y_1,y_2,\cdots,y_n)\in Y ；且k = {k_1} + {k_2}，{g_i}({\boldsymbol{x}})和{h_j}({\boldsymbol{x}})分别代表第i和第j个设计约束. 对于单目标优化问题，不同解的比较是非常直观的，更好的适应度（即目标值）意味着更好的设计方案. 但对于多目标优化问题，不同解的比较变得非常复杂，因为涉及到多个目标值间的比较和权衡，从而对探索和优化方法提出了更高要求.
3.2 相关设计空间探索方法
在处理器开发的早期阶段，需要对微架构组件的组织和组合进行探索决策，以实现PPA指标之间的良好权衡，由此产生了微架构设计空间探索问题. 在工业界，微架构设计空间探索通常是依靠架构师经验和软件模拟[27-30]来完成的. 通过处理器架构师的专家知识对设计空间进行修剪，然后选择有限的候选设计在模拟器上进行仿真和比较权衡. 然而，随着微架构设计变得越来越复杂，参数空间越来越庞大，这种方法愈发难以满足现代处理器的设计需求. 此外，由于模拟器和真实设计之间的差异以及不同设计阶段之间的设计鸿沟问题，所产生的仿真和建模误差以及人工偏见往往导致次优的解决方案. 学术界已经提出了各种方法来加速微架构设计空间探索，这些方法可以分为解析方法和基于机器学习的黑盒方法.
解析方法旨在构建轻量级的可解释模型，用函数公式描述微架构设计/工作负载与设计目标之间的关系，从而辅助设计空间剪枝或实现快速探索. Karkhanis 等人[70]通过一阶模型获得超标量处理器的性能估计，该模型结合了从功能级模拟中收集的缓存和分支预测器统计数据. 进一步地，Karkhanis等人[71]提出了一个由性能和能量活动模型以及基于模型的优化过程组成的分析框架，用以得出帕累托最优解的设计参数. RpStacks[72]有选择地从仿真中收集关键性能事件，建立一些描述执行路径延迟的事件栈，并估计整体性能以及失速事件构成. 解析方法通常需要大量的专家知识来构建轻量级模型，且精度有限、可迁移性差，难以处理不同设计下的大量设计点. Bai等人[73]通过自动瓶颈分析来规避领域知识要求，并提出了由新的微执行图表述、最佳关键路径构建算法和硬件资源重新分配策略组成的Arch-Explorer探索框架.
3.3 机器学习辅助微架构设计空间探索
构建解析模型需要大量的专业知识，且难以扩展到新型处理器. 当专家知识难以获取时，数据驱动的机器学习方法被引入. 与解析方法不同，基于机器学习的方法构建数据驱动的学习模型来表征设计空间，并进行基于学习的探索和优化，由于具有更好的预测和搜索能力，通常优于基于解析的探索方法.
早期工作将设计空间探索表述为回归问题，通过各类学习模型预测给定处理器架构配置的PPA响应，并基于PPA预测值进行决策优化. Lee 等人[51]将设计空间采样和统计学习结合起来，无需详尽的模拟就能获得变化趋势，从而在设计空间探索中实现新的功能. Ipek 等人[58-59]利用ANN来捕获硬件架构参数和PPA指标之间的关系，以此构建准确的预测模型直接进行设计空间探索. Dubach 等人[74]使用以架构为中心的方法，通过将离线训练的先验知识应用于各种基准程序，从而预测整个微架构配置空间的性能和能耗.
如图13所示，Chen等人[75]提出了ArchRanker探索框架，他们将设计空间探索问题转换为排名问题，通过训练RankBoost学习模型[76]来预测2种架构配置中哪一种的性能最佳，从而确定整个设计空间中较优的架构设计. 在单核和多核设计场景上的实验表明，相比于基于ANN回归模型的方法[59]，该排名模型需要更少的训练仿真时间.
如图14所示，Li等人[77]结合了统计采样和AdaBoost学习技术. 首先，采用基于特征选择的正交阵列（orthogonal array，OA），通过修剪对性能影响较小的参数以缩小设计空间；其次，引入基于OA的训练数据采样方法来选择代表性配置；最后，提出了一种主动学习方法ActBoost来构建预测模型，并对未探索设计的性能进行预测. 基于gem5的实验结果表明，在固定训练样本规模的情况下，该方法能够实现更高的预测精度，从而有助于实现高效、精确的设计空间探索.
![]()
如图15所示，Bai等人[78-79]提出了一个基于贝叶斯优化（Bayesian optimization，BO）的自动框架来探索BOOM微架构设计，称为BOOM-Explorer，实现了较高的探索质量和效率. 首先，该框架利用先进的微架构感知主动学习MicroAL算法来生成多样化且具有代表性的初始设计集；其次，建立具有深度核学习函数的高斯过程模型DKL-GP来表征设计空间；然后，利用相关多目标贝叶斯优化来探索帕累托最优设计，通过引入帕累托超体积期望提升来处理负相关的多目标（性能和功耗）优化；最后，提出了多样性引导的并行探索策略，并与批量贝叶斯优化流程相结合. 该框架在BOOM处理器的微架构设计空间探索中展现了较高的性能，并给出了如表3所示的具体参数选择，其微架构参数取值与表2相对应.
表 3 BOOM处理器的不同微架构设计参数选择Table 3. Design Parameters Selectivity of Different Microarchitecture for BOOM Processors然而，微架构设计空间并不平滑，设计参数的微小改动有可能引起设计指标的较大波动，这与GP模型的先验假设并不完全相符. 因此，如图16所示，Bai等人[80]将微架构设计空间探索形式化为一种多目标强化学习问题，利用微架构缩放图[81]将专家经验与强化学习方法紧密结合，使用智能代理（agent）依次确定各组件设计，并将架构师的设计偏好嵌入到方法论中，还使用轻量化的PPA评估框架构，建强化学习环境以加速收敛. Bai等人[16]在Rocket处理器和BOOM处理器上验证了该方法的有效性.
Zhai等人[82]则提出了一种帕累托驱动的主动学习方法，该方法结合参数重要性的先验知识自动选择更具代表性的初始设计，通过在迭代探索中构建基于树集成模型的动态性能和功耗模型，优先探索具有较大超体积贡献的预测帕累托设计，并允许接受较差的帕累托解来克服模型预测误差，同时使用并行策略来加速探索.
如图17所示，Yu等人[83]提出了一种基于迁移学习的探索框架IT-DSE，其代理模型经过预训练，可以吸收以往微架构设计任务中的知识. 他们将Feature Tokenizer-Transformer（FT-Transformer） 作为特征提取的骨干模型，以允许对具有不同设计空间的多个源任务进行预训练；同时，使用不变风险最小化（invariant risk minimization，IRM）来增强学习模型在不同数据分布差异下的泛化能力；最后，利用多目标贝叶斯优化和预训练模型来探索帕累托最优设计.
Yi等人[84]提出了一种基于图嵌入的微架构搜索框架GRL-DSE. 如图18所示，GRL-DSE 使用一种有向无环图（directed acyclic graph，DAG）模型[85]来表示处理器微架构硬件组织和参数关系；其次，利用图表示学习来提取关键微架构特征并构建紧凑且连续的图嵌入空间，并使用变分图自动编码器（variational graph auto-encoder，VGAE）框架训练图神经网络模型；最后，使用基于集成学习策略的代理模型完成多目标贝叶斯优化，从而在图嵌入空间中进行微架构设计空间探索. 该方法同样在BOOM处理器上进行了验证.
Wang等人[86]使用集成模型进行高精度预测，以及一种上置信界超体积提升优化方法来逼近帕累托最优集，并提出了帕累托感知的过滤算法来减少探索时间. 进一步地，Wang等人[87-88]通过集成学习增强模型AdaGBRT生成基于帕累托排序的样本权重以提高预测准确性，然后提出了一种基于超体积提升的优化方法来在多个目标之间进行权衡，并结合均匀性感知选择算法来跳出局部最优.
Esmaeilzadeh等人[89]为硬件加速深度神经网络（DNN）和非 DNN ML算法提出了一种物理设计驱动、基于学习的预测框架. 该框架采用统一的方法，将后端PPA分析与前端性能仿真相结合，从而实现对后端 PPA 、运行时间和能耗等系统指标的实际估计，通过自动搜索架构和后端参数来优化物理设计和系统指标.
Chen等人[90]提出了一种以DNN加速器为主要目标的探索框架SoC-Tuner，用于高效探索片上系统（system on chip，SoC）配置的帕累托最优集. 该框架提出了一种基于重要性的SoC设计空间剪枝和探索初始化方法，并设计了一种采样算法来选择最具代表性的初始化点，以及一种信息增益引导的多目标优化方法，从而平衡 SoC 设计的多个设计指标. 该方法在由Rocket/BOOM处理器、Gemmini加速器[91]等组成的SoC设计上进行了验证.
此外，为促进相关领域的发展，ICCAD 2022举办了以处理器微架构设计空间探索为主题的竞赛[92]. 该比赛创建了一个包含15633个不同BOOM微架构的数据集，并提供了设计空间探索算法基准测试平台，吸引了来自全球各地166个队伍的参与，在线比赛系统[93]也将长期维护下去.
3.4 小 结
在微架构设计阶段进行广泛的探索优化，有利于推动处理器设计收敛于全局最优，并减少设计迭代、降低开发成本，是实现处理器芯片跨层优化的重要途径. 然而，设计空间的复杂庞大、PPA指标评估的不准确性，以及复杂耗时的设计验证流程使得微架构设计空间探索面临极大挑战. 在这种情况下，各类机器学习模型被用于PPA预估，贝叶斯优化、主动学习、强化学习等机器学习方法被用于探索最优设计. 得益于机器学习技术强大的建模和搜索能力，上述机器学习辅助的探索方法在很多情况下更加快速地获得了更好的微架构设计.
表4从探索目标、探索方法及PPA数据来源等方面总结了机器学习辅助的微架构设计空间探索工作. 总的来说，机器学习辅助设计空间探索的一般流程如图19所示. 对于给定的设计空间，初始化方法一次性地选择最具有代表性的初始设计，并依靠EDA工具或仿真器进行进行PPA评估，进而更新数据集并训练机器学习模型，然后依靠模型预测和采样策略进行迭代探索，在探索结束时给出目标设计（集）.
表 4 基于机器学习的微架构设计空间探索方法总结Table 4. A Summary of Machine Learning-Based Methods for Microarchitecture Design Space Exploration方法/文献 探索目标 探索方法 PPA等数据来源 文献[51] 帕累托前沿、流水线深度以及异构性分析 设计空间采样、统计学习 Turandot仿真器、PowerTimer工具 文献[58−59] 设计空间的预测模型 使用ANN建模遍历子空间 SESC仿真器、CACTI等 文献[73] 设计空间的预测模型 使用ANN和线性回归建模遍历子空间 仿真器、Wattch、CACTI等 ArchRanker[75] 特定目标下最优设计 基于RankBoost排名模型遍历子空间 仿真器、Wattch、CACTI等 文献[77] 预测模型及最优设计 基于AdaBoost.RT模型和正交阵列采样 gem5仿真器 BOOM-Explorer[78−79] 帕累托最优设计 基于贝叶斯优化和深度核高斯过程建模 商业EDA工具 文献[80] 特定偏好下最优设计 基于微架构缩放图的强化学习 商业EDA工具 文献[82] 帕累托最优设计 基于集成树建模和主动学习 商业EDA工具 IT-DSE[83] 帕累托最优设计 基于贝叶斯优化、不变风险最小化和Transformer 商业EDA工具 GRL-DSE[84] 帕累托最优设计 基于图神经网络、集成模型、贝叶斯优化 商业EDA工具 文献[86] 帕累托最优设计 基于BagGBRT和上置信界超体积提升 仿真器、McPAT等工具 MoDSE[87−88] 帕累托最优设计 基于AdaGBRT和帕累托超体积提升 仿真器、McPAT等工具 文献[89] ML加速器最优设计 机器学习模型、图神经网络、贝叶斯优化 商业EDA工具 SoC-Tuner[90] SoC帕累托最优设计 设计空间剪枝、贝叶斯优化 商业EDA工具 未来，如何将微架构领域的专家知识（例如微架构组织和参数的依赖性等）与机器学习方法紧密结合，并努力提高探索框架的泛化性和可扩展性仍是需要进一步探索的问题. 除了单纯的设计参数调整外，如何利用机器学习技术反哺微架构设计，例如使用大模型辅助微架构设计生成，也是值得研究的问题.
4. 总结与展望
本文首先回顾了现代处理器设计的主要流程，以及微架构设计在“后摩尔时代”所面临的建模和优化挑战. 在此基础上，介绍了如何运用机器学习技术辅助处理器微架构功耗建模和设计空间探索问题，并就相关的具体工作展开了讨论.
更小、更快、功耗更低的计算设备将是人们永远追求的目标，随着摩尔定律的进一步放缓，微架构设计将占有更重要的地位，且面临更加严峻的挑战. 展望未来，以下3个方面依然值得进一步研究：
1）更加快速精细的功耗估计和更高的模型可迁移性. 处理器规模的不断增长和工作负载的多样化，对建模速度和精度提出了更高要求. 现有工作大多利用各种机器学习技术对微架构设计在较长时间间隔内的平均功耗进行预测，建模的精细度仍有不足、建模代价也较为高昂，所得功耗模型的可迁移性不强. 因此，如何利用先验知识降低模型的训练成本，并进一步提高功耗模型的建模粒度、可迁移性，并降低建模代价至关重要. 对于建模粒度而言，首先需要精确估计不同工作负载在更短时间粒度内的功率消耗，并为动态电压频率调整等节能技术的设计提供参考；其次是更细的硬件粒度，即如何提供不同硬件层次的精确功耗估计，增强模型可解释性，并将其用于后续热问题的建模，允许设计人员更有针对性地进行估计和优化；最后，如何提高模型在多平台、多领域架构间的可迁移性和功能完善性，并实现对异质异构集成芯片的精确建模是未来的研究方向.
2）更加高效统一的设计空间探索优化框架. 处理器的规模在不断增长，产生了大量可参数化的微架构设计参数、EDA工具参数以及诸多难以参数化的设计策略. 因此，如何将微架构探索与整个EDA设计流程内的探索优化相结合，并结合先验知识实现高维设计空间内全局最优设计的快速探索成为关键. 首先，可以考虑混合使用机器学习模型、软件仿真器和传统EDA设计流程工具进行建模及探索优化，并设计验证时间感知的调度策略. 同时，现有的设计空间探索工作多是针对静态可参数化空间进行的，如何有效地对动态的难以量化的设计选项进行探索和优化也是一个尚未解决的问题. 此外，目前的设计空间探索工具大多是面向特定设计或任务的，如何提高其在不同设计和工艺节点间的可迁移性，将不同阶段、不同任务的探索工具整合到一个统一的标准流程中，真正实现跨层次的全局优化也将是未来的研究方向.
3）高质量的公开数据集和数据获取方法. 得益于AI领域的飞速发展，机器学习技术能够有效地辅助相关问题的求解. 然而，机器学习模型通常需要大量的有标记训练数据，而传统VLSI设计流程漫长耗时，且EDA工具、先进IP核和工艺库需要昂贵的商业授权，导致缺乏针对相关任务的高质量公开数据，难以充分验证机器学习模型的泛化能力和迁移能力. 目前已有针对集成电路后端设计等任务的公开数据集，但针对处理器微架构建模和探索的数据集仍比较欠缺，多数工作基于私有数据集，或使用开源的处理器设计自行生成数据集，数据规模小、代表性不强，阻碍了机器学习技术在相关领域的进一步应用. 因此，如何利用主动学习等技术更加高效地获取数据，并建立涵盖不同处理器设计和VLSI设计阶段的公开数据集用于相关算法的设计和评估，也是值得进一步研究的问题.
考虑到相关算法的快速更新、持续增长的硬件支持能力，以及不断积累的应用数据，机器学习将与微架构设计的传统方法更加有机地结合，从而实现更加精确的建模和更加高效的探索优化.
作者贡献声明：翟建旺和余备提出了写作思路；翟建旺、凌梓超和白晨负责调研并撰写论文；赵康和余备提出指导意见并修改论文.
-
表 1 真实代码与指针分析对数组建模的对比
Table 1 Comparison of Real Code and Array Modeling of Pointer Analysis
真实代码 指针分析数组建模 array = new String[10];
array[0] = "x";
array[1] = "y";
s = array[0];array = new String[];
array.arr = "x";
array.arr = "y";
s = array.arr;
下载: 导出CSV
表 2 指针分析算法符号与域的说明
Table 2 Notations and Domains Used in Pointer Analysis Algorithm
符号 域 方法 m M 变量 x, y V 对象 oi, oj O 字段 f, g F 实例字段 oi.f, oj.g O × F 指针 s, t Pointer = V ∪ （O × F） 指向关系 pt Pointer → \cal P（O）
下载: 导出CSV
表 3 指针分析规则
Table 3 Rules for Pointer Analysis
语句种类 语句 指针分析规则 PFG边 对象创建 i: x = new T() \dfrac{ {o}_{i}={H}{e}{a}{p}\left(i\right)}{ {o}_{i}\in pt\left(x\right)} 复制 x = y \dfrac{ {o}_{i}\in pt\left(y\right)}{ {o}_{i}\in pt\left(x\right)} x\leftarrow y 字段存储 x.f = y \dfrac{ {o}_{i}\in pt\left(x\right),{o}_{j}\in pt\left(y\right)}{ {o}_{j}\in pt({o}_{i}.f)} {o}_{i}.f\leftarrow y 字段读取 y = x.f \dfrac{ {o}_{i}\in pt\left(x\right),{o}_{j}\in pt\left({o}_{i}.f\right)}{ {o}_{j}\in pt\left(y\right)} y\leftarrow {o}_{i}.f 方法调用 l: r = x.k(a1,…,an) \dfrac{\begin{array}{c}{o}_{i}\in pt\left(x\right),m=Dispatch({o}_{i},k)\\ {o}_{u}\in pt\left(a_j\right),1\le j\le n\\ {o}_{v}\in pt\left({m}_{{\rm{ret}}}\right)\end{array} }{\begin{array}{c}{o}_{i}\in pt\left({m}_{this}\right)\\ {o}_{u}\in pt\left({m}_{p_j}\right),1\le j\le n\\ {o}_{v}\in pt\left(r\right)\end{array} } \begin{gathered} a_1\to {m}_{p_1}\\ \vdots \\ a_n\to {m}_{p_n}\\ r\leftarrow {m}_{ {\rm{ret} } }\end{gathered}
下载: 导出CSV
表 4 上下文敏感指针分析算法符号与域的说明
Table 4 Notations and Domains Used in Context-Sensitive Pointer Analysis Algorithm
符号 域 上下文 c, c′, c′′ C 上下文敏感方法 c:m C × M 上下文敏感变量 c:x, c′:y C × V 上下文敏感对象 c:oi, c′:oj C × O 字段 f, g F 实例字段 c:oi.f, c′:oj.g C × O × F 上下文敏感指针 s, t CSPointer = （C × V） ∪ （C × O × F） 指向关系 pt CSPointer → \cal P （C × O）
下载: 导出CSV
表 5 上下文敏感指针分析规则
Table 5 Rules for Context-Sensitive Pointer Analysis
语句种类 语句 指针分析规则（在上下文 c 中） PFG边 对象创建 i: x = new T() \dfrac{ {o}_{i}={Heap}\left(i\right)}{ {c:o}_{i}\in pt(c:x)} 复制 x = y \dfrac{ {c}':{o}_{i}\in pt(c:y)}{ {c}':{o}_{i}\in pt(c:x)} c:x\leftarrow c:y 字段存储 x.f = y \dfrac{ {c}':{o}_{i}\in pt\left(c:x\right),{c}'':{o}_{j}\in pt\left(c:y\right)}{ {c}'':{o}_{j}\in pt({c}':{o}_{i}.f)} {c}':{o}_{i}.f\leftarrow c:y 字段读取 y = x.f \dfrac{ {c}':{o}_{i}\in pt\left(c:x\right),{c}'':{o}_{j}\in pt({c}':{o}_{i}.f)}{ {c}'':{o}_{j}\in pt(c:y)} c:y\leftarrow {c}':{o}_{i}.f 方法调用 l: r = x.k(a1,…,an) \dfrac{\begin{array}{c}{c}':{o}_{i}\in pt\left(c:x\right),\\ m=Dispatch\left({o}_{i},\mathrm{k}\right),{c}^{t}=Select(c,l,{c}':{o}_{i})\\ {c}'':{o}_{u}\in pt\left(c:aj\right),1\le j\le n\\ {c}''':{o}_{v}\in pt({c}^{t}:{m}_{{\rm{ret}}})\end{array} }{\begin{array}{c}{c}':{o}_{i}\in pt({c}^{t}:{m}_{{\rm{this}}})\\ {c}'':{o}_{u}\in pt\left({c}^{t}:{m}_{{\rm{pj}}}\right),1\le j\le n\\ {c}''':{o}_{v}\in pt(c:r)\end{array} } c:a_1\to {c}^{t}:{m}_{p_1}
\vdots
c:a_n\to {c}^{t}:{m}_{p_n}
c:r\leftarrow {c}^{t}:{m}_{{\rm{ret}}}
下载: 导出CSV
-
[1] Smaragdakis Y, Balatsouras G. Pointer analysis[J]. Foundations and Trends in Programming Languages, 2015, 2(1): 1−69 doi: 10.1561/2500000014
[2] 张健,张超,玄跻峰,等. 程序分析研究进展[J]. 软件学报,2019,30(1):80−109 doi: 10.13328/j.cnki.jos.005651 Zhang Jian, Zhang Chao, Xuan Jifeng, et al. Recent progress in program analysis[J]. Journal of Software, 2019, 30(1): 80−109 (in Chinese) doi: 10.13328/j.cnki.jos.005651
[3] Sridharan M, Chandra S, Dolby J, et al. Alias analysis for object-oriented programs [G] //LNCS 7850: Aliasing in Object-Oriented Programming. Types, Analysis and Verification. Berlin: Springer, 2013: 196−232
[4] Chandra S, Fink S J, Sridharan M. Snugglebug: A powerful approach to weakest preconditions [C] //Proc of the 30th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2009: 363−374
[5] Naik M, Aiken A, Whaley J. Effective static race detection for Java [C] //Proc of the 27th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2006: 308−319
[6] Naik M, Park C S, Sen K, et al. Effective static deadlock detection [C] //Proc of the 31st Int Conf on Software Engineering. Piscataway, NJ: IEEE, 2009: 386−396
[7] 王蕾,何冬杰,李炼,等. 基于稀疏框架的静态污点分析优化技术[J]. 计算机研究与发展,2019,56(3):480−495 doi: 10.7544/issn1000-1239.2019.20180071 Wang Lei, He Dongjie, Li Lian, et al. Sparse framework based static taint analysis optimization[J]. Journal of Computer Research and Development, 2019, 56(3): 480−495 (in Chinese) doi: 10.7544/issn1000-1239.2019.20180071
[8] Arzt S, Rasthofer S, Fritz C, et al. FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android Apps [C] //Proc of the 35th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2014: 259−269
[9] Grech N, Smaragdakis Y. P/Taint: Unified points-to and taint analysis [J]. Proceedings of the ACM on Programming Languages, 2017, 1(OOPSLA): 1−28
[10] Livshits V B, Lam M S. Finding security vulnerabilities in Java applications with static analysis [C] //Proc of the 14th USENIX Security Symp. Berkeley, CA: USENIX Association, 2005: 271−286
[11] Avots D, Dalton M, Livshits V B, et al. Improving software security with a C pointer analysis [C] //Proc of the 27th Int Conf on Software Engineering. New York: ACM, 2005: 332−341
[12] Li Yue, Tan Tian, Zhang Yifei, et al. Program tailoring: Slicing by sequential criteria [C] //Proc of the 30th European Conf on Object-Oriented Programming. Wadern, Saarland: Schloss Dagstuhl - Leibniz-Zentrum Fuer Informatik, 2016, 15: 1−15: 27
[13] Sridharan M, Fink S J, Bodík R. Thin slicing [C] //Proc of the 28th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2007: 112−122
[14] Fink S J, Yahav E, Dor N, et al. Effective typestate verification in the presence of aliasing [J]. ACM Transactions on Software Engineering and Methodology, 2008, 17(2): 1−34
[15] Pradel M, Jaspan C, Aldrich J, et al. Statically checking API protocol conformance with mined multi-object specifications [C] //Proc of the 34th Int Conf on Software Engineering. Piscataway, NJ: IEEE, 2012: 925−935
[16] Lhoták O, Smaragdakis Y, Sridharan M. Pointer analysis (Dagstuhl Seminar 13162) [R]. Wadern, Saarland: Schloss Dagstuhl - Leibniz-Zentrum Fuer Informatik, 2013
[17] Weihl W E. Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables [C] //Proc of the 7th ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 1980: 83−94
[18] Lhoták O, Hendren L J. Scaling Java points-to analysis using SPARK [G] //LNCS 2622: Proc of the 12th Int Conf on Compiler Construction. Berlin: Springer, 2003: 153−169
[19] Bravenboer M, Smaragdakis Y. Strictly declarative specification of sophisticated points-to analyses [C] //Proc of the 24th Annual ACM SIGPLAN Conf on Object-Oriented Programming, Systems, Languages, and Applications. New York: ACM, 2009: 243−262
[20] Li Yue, Tan Tian, Møller A, et al. A principled approach to selective context sensitivity for pointer analysis [J]. ACM Transactions on Programming Languages and Systems, 2020, 42(2): 1−40
[21] Andersen L O. Program analysis and specialization for the C programming language [D]. Copenhagen: University of Copenhagen, DIKU, 1994
[22] Hardekopf B, Lin C. The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code [C] //Proc of the 28th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2007: 290−299
[23] Hardekopf B, Lin C. Semi-sparse flow-sensitive pointer analysis [C] //Proc of the 36th Annual ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 2009: 226−238
[24] Yu Hongtao, Xue Jingling, Huo Wei, et al. Level by level: Making flow- and context-sensitive pointer analysis scalable for millions of lines of code [C] //Proc of the 8th Annual IEEE/ACM Int Symp on Code Generation and Optimization. New York: ACM, 2010: 218−229
[25] Sui Yulei, Xue Jingling. SVF: Interprocedural static value-flow analysis in LLVM [C] //Proc of the 25th Int Conf on Compiler Construction. New York: ACM, 2016: 265−266
[26] Hind M. Pointer analysis: Haven't we solved this problem yet? [C] //Proc of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering. New York: ACM, 2001: 54−61
[27] Gosling J, Joy B, Steele G, et al. The Java® Language Specification, Java SE 17 Edition [S/OL]. Austin, Texas: Oracle America, Inc. , 2021. [2022-10-20].https://docs.oracle.com/javase/specs/jls/se17/html/index.html
[28] Fähndrich M, Foster J S, Su Zhendong, et al. Partial online cycle elimination in inclusion constraint graphs [C] //Proc of the ACM SIGPLAN 1998 Conf on Programming Language Design and Implementation. New York: ACM, 1998: 85−96
[29] Pearce D J, Kelly P H J, Hankin C. Online cycle detection and difference propagation for pointer analysis [C] //Proc of the 3rd IEEE Int Workshop on Source Code Analysis and Manipulation. Piscataway, NJ: IEEE, 2003: 3−12
[30] Sharir M, Pnueli A. Two approaches to interprocedural data flow analysis [R]. New York: New York University, 1978
[31] Lhoták O, Hendren L J. Context-sensitive points-to analysis: Is it worth it? [G] //LNCS 3923: Proc of the 15th Int Conf on Compiler Construction. Berlin: Springer, 2006: 47−64
[32] Whaley J, Lam M S. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams[J]. ACM SIGPLAN Notices, 2004, 39(6): 131−144 doi: 10.1145/996893.996859
[33] Xu Guoqing, Rountev A. Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis [C] //Proc of the 2008 Int Symp on Software Testing and Analysis. New York: ACM, 2008: 225−236
[34] Tan Tian, Li Yue, Ma Xiaoxing, et al. Making pointer analysis more precise by unleashing the power of selective context sensitivity [J]. Proceedings of the ACM on Programming Languages, 2021, 5(OOPSLA): 1−27
[35] Tan Tian, Li Yue. Tai-e: A static analysis framework for Java by harnessing the best designs of classics [J]. arXiv preprint, arXiv: 2208,00337
[36] Tan Tian, Li Yue. Tai-e: An easy-to-learn/use static analysis framework for Java [CP/OL]. [2022-10-22].https://github.com/pascal-lab/Tai-e
[37] He Dongjie, Lu Jingbo, Xue Jingling. Qilin: A new framework for supporting fine-grained context-sensitivity in Java pointer analysis [C] //Proc of the 36th European Conf on Object-Oriented Programming. Wadern, Saarland: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2022, 30: 1−29
[38] Smaragdakis Y. Doop: Framework for Java pointer and taint analysis (using P/Taint) [CP/OL]. [2022-10-22].https://bitbucket.org/yanniss/doop
[39] Bodden E. Soot: A framework for analyzing and transforming Java and Android applications [CP/OL]. [2022-10-22]. http://soot-oss.github.io/soot/
[40] Shivers O G. Control-flow analysis of higher-order languages [D]. Pittsburgh, PA: Carnegie Mellon University, 1991
[41] Might M, Smaragdakis Y, Horn D V. Resolving and exploiting the k-CFA paradox: Illuminating functional vs. object-oriented program analysis [C] //Proc of the 31st ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2010: 305−315
[42] Milanova A, Rountev A, Ryder B G. Parameterized object sensitivity for points-to and side-effect analyses for Java [C] //Proc of the 2002 Int Symp on Software Testing and Analysis. New York: ACM, 2002: 1−11
[43] Milanova A, Rountev A, Ryder B G. Parameterized object sensitivity for points-to analysis for Java[J]. ACM Transactions on Software Engineering and Methodology, 2002, 14(1): 1−41
[44] Smaragdakis Y, Bravenboer M, Lhoták O. Pick your contexts well: Understanding object-sensitivity [C] //Proc of the 38th Annual ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 2011: 17−30
[45] Kastrinis G, Smaragdakis Y. Hybrid context-sensitivity for points-to analysis [C] //Proc of the 34th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2013: 423−434
[46] Tan Tian, Li Yue, Xue Jingling. Making k-object-sensitive pointer analysis more precise with still k-limiting [G] //LNCS 9837: Proc of the 2016 Int Static Analysis Symp. Berlin: Springer, 2016: 489−510
[47] Jeon M, Jeong S, Oh H. Precise and scalable points-to analysis via data-driven context tunneling [J]. Proceedings of the ACM on Programming Languages, 2018, 2(OOPSLA): 1−29
[48] Jeong S, Jeon M, Cha S, et al. Data-driven context-sensitivity for points-to analysis [J]. Proceedings of the ACM on Programming Languages, 2017, 1(OOPSLA): 1−28
[49] Jeon M, Oh H. Return of CFA: Call-site sensitivity can be superior to object sensitivity even for object-oriented programs [J]. Proceedings of the ACM on Programming Languages, 2022, 6(POPL): 1−29
[50] Smaragdakis Y, Kastrinis G, Balatsouras G. Introspective analysis: Context-sensitivity, across the board [C] //Proc of the 35th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2014: 485−495
[51] Li Yue, Tan Tian, Møller A, et al. Precision-guided context sensitivity for pointer analysis [J]. Proceedings of the ACM on Programming Languages, 2018, 2(OOPSLA): 1−29
[52] Lu Jingbo, Xue Jingling. Precision-preserving yet fast object-sensitive pointer analysis with partial context sensitivity [J]. Proceedings of the ACM on Programming Languages, 2019, 3(OOPSLA): 1−29
[53] Lu Jingbo, He Dongjie, Xue Jingling. Eagle: CFL-reachability-based precision-preserving acceleration of object-sensitive pointer analysis with partial context sensitivity [J]. ACM Transactions on Software Engineering and Methodology, 2021, 30(4): 1−46
[54] He Dongjie, Lu Jingbo, Gao Yaoqing, et al. Accelerating object-sensitive pointer analysis by exploiting object containment and reachability [C] //Proc of the 35th European Conf on Object-Oriented Programming. Wadern, Saarland: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2021, 16: 1−31
[55] Li Yue, Tan Tian, Møller A, et al. Scalability-first pointer analysis with self-tuning context-sensitivity [C] //Proc of the 2018 26th ACM Joint Meeting on European Software Engineering Conf and Symp on the Foundations of Software Engineering. New York: ACM, 2018: 129−140
[56] Tan Tian, Li Yue, Xue Jingling. Efficient and precise points-to analysis: Modeling the heap by merging equivalent automata [C] //Proc of the 38th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2017: 278−291
[57] Jeon M, Lee M, Oh H. Learning graph-based heuristics for pointer analysis without handcrafting application-specific features [J]. Proceedings of the ACM on Programming Languages, 2020, 4(OOPSLA): 1−30
[58] Kanvar V, Khedker U P. Heap Abstractions for Static Analysis [J]. ACM Computing Surveys, 2017, 49(2): 1−47
[59] Chen Yifan, Yang Chenyang, Zhang Xin, et al. Accelerating program analyses in Datalog by merging library facts [G] //LNCS 12913: Proc of the 2021 Int Static Analysis Symp. Berlin: Springer, 2021: 77−101
[60] IBM T. J. Watson Research Center. WALA: T. J. Watson Libraries for Analysis [CP/OL]. [2022-10-22].https://github.com/wala/WALA
[61] Hopcroft J E, Karp R M. A linear algorithm for testing equivalence of finite automata [R]. Ithaca, NY: Cornell University, 1971
[62] Späth J, Do L N Q, Ali K, et al. Boomerang: Demand-driven flow- and context-sensitive pointer analysis for Java [C] //Proc of the 30th European Conf on Object-Oriented Programming. Wadern, Saarland: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, 22: 1−26
[63] Livshits B, Sridharan M, Smaragdakis Y, et al. In defense of soundiness: A manifesto[J]. Communications of the ACM, 2015, 58(2): 44−46 doi: 10.1145/2644805
[64] Rastogi V, Chen Yan, Jiang Xuxian. DroidChameleon: Evaluating Android anti-malware against transformation attacks [C] //Proc of the 8th ACM SIGSAC Symp on Information, Computer and Communications Security. New York: ACM, 2013: 329−334
[65] Landman D, Serebrenik A, Vinju J J. Challenges for static analysis of Java reflection: Literature review and empirical study [C] //Proc of the IEEE/ACM 39th Int Conf on Software Engineering. Piscataway, NJ: IEEE, 2017: 507−518
[66] Barros P, Just R, Millstein S, et al. Static analysis of implicit control flow: Resolving Java reflection and Android intents (T) [C] //Proc of the 30th IEEE/ACM Int Conf on Automated Software Engineering. Piscataway, NJ: IEEE, 2015: 669−679
[67] Livshits B, Whaley J, Lam M S. Reflection analysis for Java [G] //LNCS 3780: Proc of the 2005 Asian Symp on Programming Languages and Systems. Berlin: Springer, 2005: 139−160
[68] Li Yue, Tan Tian, Sui Yulei, et al. Self-inferencing reflection resolution for Java [G] //LNCS 8586: Proc of the 2014 European Conf on Object-Oriented Programming. Berlin: Springer, 2014: 27−53
[69] Li Yue, Tan Tian, Xue Jingling. Effective soundness-guided reflection analysis [G] //LNCS 9291: Proc of the 2015 Int Static Analysis Symp. Berlin: Springer, 2015: 162−180
[70] Li Yue, Tan Tian, Xue Jingling. Understanding and analyzing Java reflection [J]. ACM Transactions on Software Engineering and Methodology, 2019, 28(2): 1−50
[71] Oracle America, Inc. . Java Native Interface Specification Contents [S/OL]. Austin, Texas: Oracle America, Inc., 2021 [2022-10-22].https://docs.oracle.com/en/java/javase/17/docs/specs/jni/index.html
[72] Fourtounis G, Triantafyllou L, Smaragdakis Y. Identifying Java calls in native code via binary scanning [C] //Proc of the 29th ACM SIGSOFT Int Symp on Software Testing and Analysis. New York: ACM, 2020: 388−400
[73] Christakis M, Bird C. What developers want and need from program analysis: An empirical study [C] //Proc of the 31st IEEE/ACM Int Conf on Automated Software Engineering. New York: ACM, 2016: 332−343
[74] Bravenboer M, Smaragdakis Y. Exception analysis and points-to analysis: Better together [C] //Proc of the 18th Int Symp on Software Testing and Analysis. New York: ACM, 2009: 1−12
[75] Kastrinis G, Smaragdakis Y. Efficient and effective handling of exceptions in Java points-to analysis [G] //LNCS 7791: Proc of the 2013 Int Conf on Compiler Construction. Berlin: Springer, 2013: 41−60
[76] Fourtounis G, Smaragdakis Y. Deep static modeling of invoke dynamic [C] //Proc of the 33rd European Conf on Object-Oriented Programming. Wadern, Saarland: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, 15: 1−28
[77] Heintze N, Tardieu O. Demand-driven pointer analysis [C] //Proc of the 2001 ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2001: 24−34
[78] Sridharan M, Gopan D, Shan L, et al. Demand-driven points-to analysis for Java [C] //Proc of the 20th Annual ACM SIGPLAN Conf on Object-Oriented Programming, Systems, Languages, and Applications. New York: ACM, 2005: 59−76
[79] Sridharan M, Bodík R. Refinement-based context-sensitive points-to analysis for Java [C] //Proc of the 27th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2006: 387−400
[80] Yan Dacong, Xu Guoqing, Rountev A. Demand-driven context-sensitive alias analysis for Java [C] //Proc of the 2011 Int Symp on Software Testing and Analysis. New York: ACM, 2011: 155−165
[81] Xu Guoqing, Rountev A, Sridharan M. Scaling CFL-reachability-based points-to analysis using context-sensitive must-not-alias analysis [G] //LNCS 5653: Proc of the 2009 European Conf on Object-Oriented Programming. Berlin: Springer, 2009: 98−122
[82] Shang Lei, Xie Xinwei, Xue Jingling. On-demand dynamic summary-based points-to analysis [C] //Proc of the 10th Int Symp on Code Generation and Optimization. New York: ACM, 2012: 264−274
[83] Reps T, Horwitz S, Sagiv M. Precise interprocedural dataflow analysis via graph reachability [C] //Proc of the 22nd ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 1995: 49−61
[84] Lu Yi, Shang Lei, Xie Xinwei, et al. An incremental points-to analysis with CFL-reachability [G] //LNCS 7791: Proc of the 2013 Int Conf on Compiler Construction. Berlin: Springer, 2013: 61−81
[85] Liu Bozhen, Huang J, Rauchwerger L. Rethinking incremental and parallel pointer analysis [J]. ACM Transactions on Programming Languages and Systems, 2019, 41(1): 1−31
[86] Liu Bozhen, Huang J. SHARP: Fast incremental context-sensitive pointer analysis for Java [J]. Proceedings of the ACM on Programming Languages, 2022, 6(OOPSLA1): 1−28
计量
- 文章访问数: 609
- HTML全文浏览量: 79
- PDF下载量: 223
