改善数据高速缓存性能的方法和设备转让专利
申请号 : CN200510077097.7
文献号 : CN100583040C
文献日 : 2010-01-20
发明人 : 崔世民 , 罗奇·乔治斯·阿香博 , 劳尔·埃斯特班·西尔弗拉 , 高耀清
申请人 : 国际商业机器公司
摘要 :
本发明的机制提供了过程间的强度缩量以改善数据高速缓存的性能。在正推法期间，本发明收集全局变量的信息并且分析全局对象的使用方式以便选择用于优化的候选计算。在逆推法期间本发明将全局对象重新映射到较小大小的新的全局对象并且通过用较小的全局对象的间接的或索引的引用来代替候选计算，并且插入引用候选全局对象的每个计算的新全局对象的存储操作，产生高速缓存效率更高的代码。
权利要求 :
1.一种在数据处理系统中用于改善数据高速缓存性能的方法， 该方法包括：在正推法期间在软件程序中收集至少一个全局对象的信息，其 中所述全局对象是全局动态对象和全局阵列之一；
在所述正推法之后分析所收集的信息以形成分析信息；并且使用所述分析信息在逆推法期间修改所述软件程序的中间格式 文件，其中，所述收集步骤包括：
识别至少一个用于优化的候选全局对象；以及收集至少一个计算，所述至少一个计算在所述至少一个候选 全局对象上运行，并且其中，所述分析步骤包括：
根据所述至少一个计算中的哪个计算具有比当前计算更 低的预计算成本，来从所述至少一个计算中选择至少一个候选 计算。
2.如权利要求1的方法，其中所述收集步骤还包括：使用转义分析来分析所述至少一个全局对象的别名；以及收集至少一个存储操作，所述至少一个存储操作修改所述至少一 个候选全局对象。
3.如权利要求1的方法，其中所述分析步骤还包括：根据别名信息来完成至少一个候选全局对象；以及创建所述选择的候选计算的至少一个全局变量，其中所述至少一 个候选计算和所述至少一个全局变量是所述分析信息的一部分。
4.如权利要求3的方法，其中为所述所选的候选计算而产生的 全局变量的数目依赖于与所述至少一个候选全局对象相关联的间接 的和索引的引用之一的级别的数量。
5.如权利要求3的方法，其中该修改步骤包括：由所述至少一个全局变量的间接的或索引的引用之一来代替所 述所选的候选计算；以及对于每个所述至少一个候选全局对象，在所述软件程序中的所述 至少一个候选全局对象的所有定义点处插入存储操作。
6.如权利要求2的方法，其中所述识别步骤包括：排除可以在未定义的过程中修改的全局对象；
确定能否识别所述至少一个全局对象的准确别名；
如果能识别所述至少一个全局对象的准确别名，则分析所述至少 一个全局对象的大小；以及如果所述至少一个全局对象的大小为大，则选择所述至少一个全 局对象。
7.如权利要求6的方法，其中用于对至少一个全局对象的大小 进行分析的分析步骤是通过使用从所述软件程序的静态数据流和运 行时间配置文件之一所得到的信息来进行的。
8.如权利要求2的方法，其中所述收集至少一个计算以及至少 一个存储操作包括：确定计算是否只包括全局对象；
如果该计算只包括全局对象，则确定所述计算是否能够映射到较 小大小的数据类型的简单装载；并且如果所述计算能够映射到较小大小的数据类型的简单装载，则将 排除索引信息的计算添加到使用列表。
9.如权利要求8的方法，还包括：
确定所述至少一个候选全局对象是否是全局对象；以及如果所述至少一个候选全局对象是全局对象，则将间接和索引的 引用之一的所有级别添加到定义列表。
10.如权利要求9的方法，还包括：
如果所述至少一个候选全局对象不是全局对象，则确定所述至少 一个候选全局对象是否是全局阵列；并且如果所述至少一个候选全局对象是全局阵列，则将索引引用符号 添加到定义列表。
11.如权利要求8的方法，其中用以确定所述计算能否映射到较 小大小的数据类型的简单装载的所述确定步骤包括：确定由所述计算引用的所有全局对象的值是否在范围内；以及如果由所述计算引用的所有全局对象的值在范围内，则选择所述 计算。
12.如权利要求11的方法，还包括：
如果由所述计算引用的所有全局对象的值不在范围内，则确定该 计算是否是转换表达式，其中所述转换表达式是将包含所述至少一 个全局对象的表达式的类型和精度之一转换为较小的数据类型；并 且如果所述计算是转换成较小数据类型的转换表达式，则选择所述 计算。
13.如权利要求12的方法，还包括：
如果所述计算不是转换表达式，则确定所述计算是否是比较表达 式；并且如果所述计算是比较表达式，则选择该计算。
14.如权利要求13的方法，还包括：
如果所述计算不是比较表达式，则确定所述计算是否没有以其他 方式用于所述计算的同一循环和控制流区域之一中；以及如果所述计算没有以其他方式用于所述计算的同一循环和控制 流区域之一中，则选择该计算。
15.如权利要求3的方法，其中所述选择步骤包括：确定计算的预计算的总成本；以及
如果由所述计算引用的所述至少一个候选全局对象大小为大并 且所述计算的执行成本比由所述计算引用的所述至少一个候选全局 对象的执行成本实质上要高，则选择该计算。
16.如权利要求5的方法，其中所述插入步骤包括：如果所述选择的候选计算是对所述至少一个候选全局对象的间 接的和索引的引用之一的最高级别的存储操作，则插入至少一个候 选全局变量计算值的间接的和索引的引用之一的最高级别的存储操 作。
17.如权利要求16的方法，还包括：
如果所述选择的候选计算对所述至少一个候选全局动态对象的 间接引用的第二高级别分配存储，则插入存储操作以向所述至少一 个全局变量的间接引用的第二高级别分配较小大小的存储。
18.如权利要求17的方法，还包括：
如果所述选择的候选计算对所述至少一个候选全局动态对象的 间接引用指针的基础指针或较低级别分配存储，则插入存储操作以 向所述至少一个全局变量的间接引用指针的基础指针或较低级别分 配同样大小的存储。
19.如权利要求18的方法，还包括：
如果所述选择的候选计算为所述至少一个候选全局对象的指针 赋值，则通过用所述至少一个全局变量及其相应的别名代替所述选 择的候选计算来插入所述至少一个全局变量的存储操作。
20.一种用于改善数据高速缓存性能的数据处理系统，该数据处 理系统包括：收集装置，用于在正推法期间在软件程序中收集至少一个全局 对象的信息，其中所述全局对象是全局动态对象和全局阵列之一；
分析装置，用于在所述正推法之后分析所收集的信息以形成分析 的信息；以及修改装置，用于使用所述分析的信息在逆推法期间修改所述软件 程序的中间格式文件，其中，所述收集装置包括：
识别设备，用来识别至少一个用于优化的候选全局对象； 以及收集设备，用来收集至少一个计算，所述至少一个计算在 所述至少一个候选全局对象上运行，并且其中，所述分析装置包括：
选择设备，用来根据所述至少一个计算中的哪个计算具有 比当前计算更低的预计算成本，来从所述至少一个计算中选择 至少一个候选计算。
21.如权利要求20的数据处理系统，其中所述收集装置还包括：分析设备，用来使用转义分析来分析所述至少一个全局对象的别 名；
并且其中，所述收集设备还用来收集至少一个存储操作，所述至 少一个存储操作修改所述至少一个候选全局对象。
22.如权利要求20的数据处理系统，其中所述分析装置还包括：完成设备，用于根据别名信息来完成至少一个候选全局对象；以 及创建设备，用于对于所选的候选计算创建至少一个全局变量，其 中所述至少一个候选计算和所述至少一个全局变量是所述分析信息 的一部分。
23.如权利要求21的数据处理系统，其中所述收集设备包括：第一确定装置，用于确定计算是否只包括全局对象；
第二确定装置，如果该计算只包括全局对象，则该第二确定装置 确定所述计算是否能够映射到较小大小的数据类型的简单装载；并 且添加装置，如果所述计算能够映射到较小大小的数据类型的简单 装载，则该添加装置将排除索引信息的所述计算添加到使用列表。
24.如权利要求22的数据处理系统，其中所述选择设备包括：确定装置，用于确定计算的预计算的总成本；以及选择装置，如果由所述计算引用的所述至少一个候选全局对象的 大小为大并且所述计算的执行成本实质上高于由所述计算引用的所 述至少一个候选全局对象的执行成本，则该选择装置选择该计算。
说明书 :
技术领域
本发明涉及一种改善的数据处理系统。特别地，本发明涉及改善 数据处理系统的数据高速缓存的性能。更特别地，本发明涉及使用 全局对象的过程间强度缩量来改善数据高速缓存的性能。
背景技术
在数据处理系统中，数据高速缓存是连接处理器和主存储器的高 速缓存的一部分。每当请求例如变量值的一段数据时，处理器在主 存储器中进行查找之前会将该数据定位在数据高速缓存上。这样， 数据高速缓存存储处理器最常检索的数据。
然而，随着处理器速度的增加，由于处理器处理请求的速度远快 于数据随机存取存储器(DRAM)的处理速度，因而DRAM或数据 高速缓存的延迟也增加了。这使得改善数据高速缓存的性能成为现 代编译器设计的优先考虑。
已经介绍了用以优化全局数据定位的两种主要方法，其依次改善 了数据高速缓存的性能。一种方法使用了采用空间定位的编码转换。 在编译器的编码优化阶段期间执行该方法。通常的编码转换包括循 环分片，条状开采和循环交换。另一个方法是使用采用了数据再利 用的数据布局转换。通常的布局转换包括阵列填充和数据重建。
如通过参考引入本申请的，名为“使用过程间强度缩量来优化软 件程序的方法和设备”的相关专利申请中所提到的，成本高的计算 可以被识别并代之以成本较低的计算。这样，软件程序中的计算总 量就在过程间得到了减少并且软件程序的性能得到了提高。
然而，在程序的给定过程间角度需要一种改善数据高速缓存效用 的解决方案。因此，具有一个能够解析软件程序中的全局对象的使 用方式并且识别对象压缩时机的改善的方法和设备是很有利的，这 样就能够产生高速缓存效率更高的代码。
然而，随着处理器速度的增加，由于处理器处理请求的速度远快 于数据随机存取存储器(DRAM)的处理速度，因而DRAM或数据 高速缓存的延迟也增加了。这使得改善数据高速缓存的性能成为现 代编译器设计的优先考虑。
已经介绍了用以优化全局数据定位的两种主要方法，其依次改善 了数据高速缓存的性能。一种方法使用了采用空间定位的编码转换。 在编译器的编码优化阶段期间执行该方法。通常的编码转换包括循 环分片，条状开采和循环交换。另一个方法是使用采用了数据再利 用的数据布局转换。通常的布局转换包括阵列填充和数据重建。
如通过参考引入本申请的，名为“使用过程间强度缩量来优化软 件程序的方法和设备”的相关专利申请中所提到的，成本高的计算 可以被识别并代之以成本较低的计算。这样，软件程序中的计算总 量就在过程间得到了减少并且软件程序的性能得到了提高。
然而，在程序的给定过程间角度需要一种改善数据高速缓存效用 的解决方案。因此，具有一个能够解析软件程序中的全局对象的使 用方式并且识别对象压缩时机的改善的方法和设备是很有利的，这 样就能够产生高速缓存效率更高的代码。
发明内容
提供一种方法，设备和计算机指令以使用全局对象的过程间强度 缩量来改善数据高速缓存的性能。本发明的机制使用在正推法期间 收集的信息分析源程序中全局对象的使用方式并且确定全局对象能 否被映射到大小较小的全局对象。一旦识别出候选计算，本发明的 机制就在逆推法期间修改源程序的中间代码从而用大小较小的新的 全局对象的间接或索引的引用来代替候选计算并且对于每个引周候 选全局变量的计算向新的全局对象插入存储操作。
附图说明
在所附的权利要求书中陈述了认为是本发明特点的新颖特征。然 而最好通过联系附图参考下述对于说明性实施例的详细描述，理解 发明本身、优选实施方式以及进一步的目的和优点。其中：
图1描述了能够实施本发明的数据处理系统的网络的示意图；
图2是数据处理系统的方框图，根据本发明的优选实施例其能够 用作服务器；
图3是说明可以实施本发明的数据处理系统的方框图；
图4是说明在本发明的优选实施例中源程序、编译器和机器语言 指令之间的关系的方框图；
图5是根据本发明的优选实施例使用过程间强度缩量优化软件 程序的处理的流程图；
图6A是根据本发明的优选实施例的在正推法期间收集信息的处 理的流程图；
图6B是根据本发明的优选实施例的使用过程间的别名分析来识 别候选全局对象的处理的流程图；
图6C是根据本发明的优选实施例收集全局对象的存储操作以及 全局对象的计算的处理的流程图；
图6D是根据本发明的优选实施例的确定一个计算能否映射到较 小数据类型的简单加载的处理的流程图；
图7A是根据本发明的优选实施例分析收集的信息的处理的流程 图；
图7B是根据本发明的优选实施例的根据成本分析为强度缩量选 择候选计算以及为候选计算创建全局变量的处理的流程图；
图8A是根据本发明的优选实施例在逆推法期间修改代码的中间 表达的处理的流程图；
图8B是根据本发明的优选实施例对每个引用全局变量的计算插 入存储操作的处理的流程图；
图9是说明根据本发明的优选实施例在使用过程间强度缩量的 优化之前的示例性软件程序的示意图；
图10是说明根据本发明的优选实施例在使用过程间强度缩量的 优化之后的示例性软件程序的示意图；
图11是说明根据本发明的优选实施例在使用过程间强度缩量的 进一步优化之后的示例性软件程序的示意图；
图1描述了能够实施本发明的数据处理系统的网络的示意图；
图2是数据处理系统的方框图，根据本发明的优选实施例其能够 用作服务器；
图3是说明可以实施本发明的数据处理系统的方框图；
图4是说明在本发明的优选实施例中源程序、编译器和机器语言 指令之间的关系的方框图；
图5是根据本发明的优选实施例使用过程间强度缩量优化软件 程序的处理的流程图；
图6A是根据本发明的优选实施例的在正推法期间收集信息的处 理的流程图；
图6B是根据本发明的优选实施例的使用过程间的别名分析来识 别候选全局对象的处理的流程图；
图6C是根据本发明的优选实施例收集全局对象的存储操作以及 全局对象的计算的处理的流程图；
图6D是根据本发明的优选实施例的确定一个计算能否映射到较 小数据类型的简单加载的处理的流程图；
图7A是根据本发明的优选实施例分析收集的信息的处理的流程 图；
图7B是根据本发明的优选实施例的根据成本分析为强度缩量选 择候选计算以及为候选计算创建全局变量的处理的流程图；
图8A是根据本发明的优选实施例在逆推法期间修改代码的中间 表达的处理的流程图；
图8B是根据本发明的优选实施例对每个引用全局变量的计算插 入存储操作的处理的流程图；
图9是说明根据本发明的优选实施例在使用过程间强度缩量的 优化之前的示例性软件程序的示意图；
图10是说明根据本发明的优选实施例在使用过程间强度缩量的 优化之后的示例性软件程序的示意图；
图11是说明根据本发明的优选实施例在使用过程间强度缩量的 进一步优化之后的示例性软件程序的示意图；
具体实施方式
现在参考附图，图1描述了能够实施本发明的数据处理系统的网 络的图示。网络数据处理系统100是其中可以实施本发明的计算机 网络。网络数据处理系统100包括网络102，用以提供在网络数据处 理系统100中连接在一起的各种设备和计算机之间的通信链路。网 络102可以包括例如有线、无线通信链路或光缆的连接。
在所描述的例子中，服务器104与存储单元106一起连接到网络 102。另外，客户108，110和112连接到网络102上。这些客户108、 110和112可以是，例如，个人计算机或网络计算机。在所描述的例 子中，服务器104提供例如引导文件、操作系统图像和应用程序的 数据到客户108-112。客户108、110和112是服务器104的客户。 网络数据处理系统100可以包括未示出的附加的服务器、客户及其 他设备。在所描述的例子中，网络数据处理系统100是具有代表着 全球网络和网关，并使用传输控制协议/互联网协议(TCP/IP)协议 组进行互相通信的网络102的互联网。互联网的中心是主节点或主 计算机之间的高速数据通信线的中枢，这些主节点或主计算机由成 千上万个发送数据和信息的商业的、政府的、教育的以及其他的计 算机系统组成。当然，网络数据处理系统100也可以由多个不同类 型的例如内联网、局域网(LAN)或广域网(WAN)的网络来实现。 图1意图作为例子而不是作为本发明的结构限制。
参考图2，根据本发明的优选实施例描述了其能够实现为例如图 1中的服务器104的服务器的数据处理系统的方框图。数据处理系统 200可以是对称多处理器(SMP)系统，该系统包括连接到系统总线 206的多个处理器202和204。可选择地，可以使用单个处理器系统。 存储控制器/高速缓存208也连接到系统总线206，208提供到本地存 储器209的接口。I/O总线桥接器210连接到系统总线206并且提供 到I/O总线212的接口。存储控制器/高速缓存208和I/O总线桥接 器210可以如描述的那样集成在一起。
连接到I/O总线212的外围部件互连(PCI)总线桥接器214提 供到PCI本地总线216的接口。多个调制解调器可以连接到PCI本 地总线216。典型的PCI总线的实现将支持四个PCI扩展槽或附加连 接器。图1中到客户108-112的通信链路可通过调制解调器218和通 过附加连接器连接到PCI本地总线216的网络适配器220来提供。
附加的PCI总线桥接器222和224向附加的PCI本地总线226 和228提供接口，通过其可以支持附加的调制解调器或网络适配器。 以这种方式，数据处理系统200允许到多网络计算机的连接。如图 所示存储器映射图形适配器230和硬盘232也可以直接或间接地连 接到I/O总线212。
本领域普通技术人员将理解图2中描述的硬件可以变化。例如， 例如光盘驱动器等的外围设备也可以附加于或代替所述的硬件来使 用。所述例子不意味着对于本发明的结构限制。
图2中描述的数据处理系统可以是例如IBM eServerTM 系统，该系统是位于纽约阿蒙德的美国国际商用机器公司的产品， 运行着高级交互执行程序操作系统或LINUXTM操作系统。
IBM，eServer，Pseries和AIX是美国国际商用机器公司的商标或 注册商标。LINUX是Linus Torvalds的商标。
现在参考图3，其为描述了可以实施本发明的数据处理系统的方 框图。数据处理系统300是客户计算机的例子。数据处理系统300 采用外围部件互连(PCI)本地总线结构。虽然所述的例子采用了PCI 总线，但是也可以使用例如图形加速端口(AGP)和工业标准结构 (ISA)的其他总线结构。处理器302和主存储器304通过PCI桥接 器308连接到PCI本地总线306。PCI桥接器308也可以包括对于处 理器302的集成存储控制器和高速缓存。通过直接元件互连或通过 附加板可以形成到PCI本地总线306的附加连接。在所述的例子中， 局域网(LAN)适配器310、SCSI主机总线适配器312和扩展总线 接口314通过直接元件连接而连接到PCI本地总线306。相反，音频 适配器316、图形适配器318以及音频/视频适配器319通过插入到 扩展槽的附加板而连接到PCI本地总线306。扩展总线接口314为键 盘和鼠标适配器320、调制解调器322和附加的存储器324提供连接。 小型计算机系统接口(SCSI)主机总线适配器312为硬盘驱动器326、 磁带驱动器328和CD-ROM驱动器330提供连接。典型的PCI本地 总线的实现将支持三或四个PCI扩展槽或附加连接器。
操作系统运行在处理器302上并且用于对图3中的数据处理系统 300内的各种元件进行协调并提供控制。该操作系统可以是商用的操 作系统，例如从微软公司可得到的WindowsTM XP。Windows是微软 公司的商标。例如Java的面向对象的程序设计系统可以与操作系统 一起运行并且从在数据处理系统300上执行的Java程序或应用向操 作系统提供调用。“Java”是Sun微系统公司的商标。操作系统、面 向对象的程序设计系统以及应用程序或程序的指令位于例如硬盘驱 动器326的存储设备上并且可以装载进主存储器304中由处理器302 执行。
本领域技术人员将理解图3中的硬件可以依据实现方式而变化。 其他的内部硬件或外围设备，例如闪速只读存储器ROM，等效非易 失性存储器或光盘驱动器等，可以附加于或代替图3中描述的硬件 来使用。而且，本发明的处理可以应用于多处理器数据处理系统。
作为另外一个例子，数据处理系统300可以为独立系统，该独立 系统配置为可引导的，而不依赖于某种类型的网络通信接口。作为 又一个例子，数据处理系统300可以是个人数字助理(PDA)设备， 其配置有ROM和/或闪速ROM以提供存储操作系统文件和/或用户 产生的数据的非易失性存储器。
图3中描述的例子和上述例子不意味着暗示结构的限制。例如， 数据处理系统300除了采取PDA形式也可以是笔记本电脑或手提电 脑。数据处理系统300也可以是公共咨讯站或网络设备(Web appliance)。
本发明提供了一种使用全局对象的过程间强度缩量来改善数据 高速缓存的性能的方法、设备以及计算机指令。本发明的机制通过 压缩或预计算全局对象来减少在软件程序循环中重复引用的全局对 象的大小。全局对象包括全局动态对象和全局阵列。
对象压缩减小了高速缓存在热点的消耗并且提高了有效高速缓 存的块大小以及有效高速缓存容量。预计算通过利用处理器专用硬 件减少了在强度上的计算成本。
本发明的机制执行二重分析。该二重分析包括在正推法程序中遍 历软件程序的中间格式文件以收集信息。中间格式文件包括调用图、 控制流图和数据流图。也可以使用其它类型的中间格式文件。
在正推法期间，本发明的机制以逆深度优先顺序或从上到下的顺 序遍历调用图以收集软件程序中全局变量的定义和使用该信息。定 义信息保留了在程序中存储所有全局变量的痕迹。使用信息保留了 作为成本预算的候选的高成本计算的痕迹。
另外，本发明的机制使用转义分析来分析全局对象的别名，并且 识别对于对象压缩或预算的候选全局对象。转义分析是一种可以用 来确定全局对象的别名，即确定两个全局对象可否涉及存储器中的 同一位置的技术。任何作为自变量或返回值通过的对象由定义进行 转义。当一个对象转义了，这意味着它已经暴露在现有程序的外边 了。如果能确定全局对象的准确别名，则全局对象可以是对象压缩 的候选。使用位矢量列出候选全局对象。在遍历调用图期间改进该 候选列表并且在遍历结束时完成该列表。
当识别出候选全局对象时，本发明的机制向使用列表添加代表引 用全局对象的计算的树状输入。排除全局对象的索引，因为它们可 以在本地变量上操作并且是不需要的。如果在候选计算中引用的全 局变量是全局动态对象，那么除了树形计算，所有级别的间接引用 符号也添加到该使用列表。如果引用的全局变量是全局阵列，本发 明的机制就添加索引的引用符号到定义列表。
一旦识别出候选全局对象并且收集了定义和使用信息，本发明的 机制就在遍历完调用图所有的节点之后在正推法的结尾分析该信 息。该分析包括根据完成的别名信息来完成对于对象压缩或预计算 的全局对象候选，以及根据整个程序的成本分析来识别对于强度缩 量的候选计算。
如果一个计算只包含全局对象则该计算可以确定为对象压缩的 候选，其中引用的全局对象的索引可以包含本地变量。当且仅当一 个候选计算能够映射到大小较小的数据类型的对象的简单装载时， 该计算也可以确定为对象压缩的候选。
关于优化的候选计算，例如，如果预计算的总成本比当前计算成 本低很多，计算的预计算可能为有利。预计算的总成本由两个因素 确定：计算和实现定义的执行量，以及如果全局变量是动态对象或 阵列时，引用的全局变量的总大小。
识别候选计算之后，本发明的机制产生新的全局变量。全局变量 的大小依赖于计算中对于全局变量的间接或索引的引用的级别数。 对于最高级的间接引用的新的全局变量而具有能够根据结构保持计 算的数值范围的大小最小或较小的类型。对于全局变量的别名对象 也产生新的符号。别名对象之间的关系也被记录以用于别名分析。
在产生新的全局变量之后，本发明的机制修改在逆推法期间所编 译代码的中间格式文件。在逆推法期间，本发明的机制以深度优先 顺序或从下到上的顺序遍历中间格式文件的调用图。
本发明的机制通过用新的全局动态对象或阵列的间接的或索引 的引用代替候选计算的所有具体值来修改中间格式文件。关于候选 全局对象，本发明的机制在软件程序中对于每个引用了候选全局对 象的计算向新的全局变量在其所有的定义点插入一个存储操作，在 其定义点处定义了基础符号、间接或索引的引用符号或其别名符号。
这样，本发明提供了过程间的强度缩量方法，该方法改善了数据 高速缓存的性能。本发明预行计算源程序中的预计算的总成本并且 确定计算是否是优选的候选。然后本发明在过程间中以新的全局对 象的间接引用或新的全局阵列的索引的引用来代替候选计算，这样 就减小在软件程序循环中重复引用的全局对象的大小。
现在转向图4，即在本发明的优选实施例中描述了说明源程序、 编译器和机器语言指令之间的关系的方框图。如图4中所说明的， 在这个说明性例子中，例如程序员的用户可以定义源程序400。源程 序400包括变量和过程。
变量可以是全局的或本地的。全局变量可以由源程序400内的任 何过程存取。在本例中，变量a 406定义为浮点型而变量b 407定义 为整型。变量a 406和变量b 407都可由过程foo 408和过程bar 412 存取。在过程中，可能出现本地变量。在本例中，变量i 410在过程 foo408中定义为整型并且只在过程foo 408中可存取。
一旦确定了源程序400，程序员就可以用编译器402编译源程序 400。编译器402可以在例如图2中的数据处理系统200或图3中的 数据处理系统300的数据处理系统中实现。在编译处理中，编译器 402分几个阶段处理源程序400：词法分析阶段414、语法分析阶段 416、中间格式文件阶段418、代码优化阶段420和代码产生阶段422。
词法分析阶段414分析源程序400。在该阶段，编译器402读出 源程序400中的字符并且把它们分组进代表着逻辑内聚的字符串， 例如标识符、操作符和关键词的令牌流中。
语法分析416在令牌串上施加一个层次结构。在语法分析416 期间，编译器402从词法分析414中获得令牌串并且通过进行从上 到下或从下到上的剖析来确定该串是否是源程序的有效结构。
一旦完成了词法分析和语法分析，编译器402产生源程序400 的明确的中间代码418，该代码可以采取各种形式。例如，一个中间 代码可以是调用图、数据流图或控制流图。在优选实施例中，本发 明的机制对由编译器402产生的调用图进行二重遍历。然而，也可 以使用其它中间格式文件。
在编码优化阶段420中，编译器402进行各种转换以改善中间编 码。这些转换包括例如循环分片或条状开采的循环转换。这些转换 改善了目标机器代码的性能。
最后，编译器402通过对程序使用的每个变量选择存储位置产生 目标机器代码。每个中间指令被翻译成机器语言指令串，例如执行 同一任务的机器语言指令404。机器语言指令404可以用于例如 平台的具体平台。UNIX是Open Group的注册商标。然后程 序员可以以改善的性能在具体平台上执行这些指令。
现在转向图5，即根据本发明的优选实施例描述了使用内部程序 的强度缩量来优化软件程序的处理的流程图。当如图4的编译器402 的编译器产生一个源程序的中间代码时处理开始(步骤502)。产生 的中间格式文件可以是调用图、控制流图或数据流图。
接着，本发明的机制在正推法期间收集包括全局变量的使用和定 义信息的信息(步骤504)。正推法是以逆深度优先或从上到下的顺 序遍历调用图。一旦收集了信息，本发明的机制就在遍历完调用图 的所有节点之后在正推法结束时分析收集的信息(步骤506)。
最后，本发明的机制在逆推法期间修改编译代码的中间格式文件 (步骤508)。逆推法是以深度优先或从下到上的顺序遍历调用图。 其后处理结束。通过使用二重分析，通过增加更新标记有每个程序 最小计算数目的引用而避免了冗余计算。
现在转向图6A，即描述了根据本发明的优选实施例的在正推法 期间收集信息的处理的流程图。该处理更加详细地描述了图5中的 步骤504。如图6A所描述的，当本发明的机制以深度优先顺序或从 上到下的顺序遍历由编译器产生的中间格式文件时，处理开始了(步 骤602)。
接着，本发明的机制使用全局对象的过程间别名分析来识别候选 全局对象(步骤604)。在识别了候选全局对象之后本发明的机制收 集对全局对象的存储操作和全局对象的计算(步骤606)。全局对象 的计算收集在使用列表中并且对全局对象的存储操作收集在定义列 表中。一旦产生使用列表和定义列表，之后该处理结束。
现在转向图6B，即根据本发明的优选实施例描述了使用过程间 的别名分析来识别候选全局对象的处理的流程图。该处理更加详细 地描述了图6A中步骤604的处理。如图6B所描述的，当本发明的 机制排除了可以在未定义的程序中修改的全局变量时，处理开始(步 骤608)。
定义的程序是具有相应的中间格式文件的程序。如果一个程序的 中间格式文件是不可得的，则该程序被识别为未定义程序。一个未 定义程序的例子包括将汇编代码链接到编译代码的程序。未定义程 序中的全局变量被排除，这是因为在这样的程序中不可能进行预计 算。
接着，本发明的机制使用转义分析来分析全局动态对象和阵列的 别名(步骤610)。可以确定别名的全局对象可以作为候选。然后， 本发明的机制分析全局动态对象和阵列的大小(步骤612)。全局对 象或阵列的大小可以通过静态程序数据流分析或运行时间配置文件 而得到。大小大的全局对象可以为候选。最后，由本发明的机制建 立候选全局对象的列表(步骤614)并且其后处理结束。
下面转向图6C，即根据本发明的优选实施例描述了用于收集对 于全局对象的存储操作和全局对象的计算的处理的流程图。该处理 更加详细地描述了图6A中的步骤606。
如图6C所描述的，当本发明的机制定位于下一个计算时，处理 开始(步骤620)。接着，本发明的机制确定该计算是否只包含全局 变量(步骤622)。在这种情况下，所引用的全局变量的索引可以包 含本地变量。如果该计算不只包含全局变量，则该计算可能不是潜 在的候选并且处理继续到步骤636。
如果该计算只包含全局变量，则本发明的机制确定该计算能否映 射到一个大小较小的数据类型的简单装载(步骤624)。该步骤在图 6D中更详细的进行了说明。如果该计算不能映射到一个大小较小的 数据类型的简单装载，则处理继续到步骤636。如果该计算能映射到 一个大小较小的数据类型的简单装载，则本发明的机制向使用列表 添加代表排除索引的计算的树(步骤626)，因为该索引是不需要的。
在添加了代表计算的树之后，本发明的机制确定在本计算中引用 的全局变量是否是全局动态对象(步骤628)。如果该全局变量是全 局动态对象，则本发明的机制不只将基础对象还将间接引用符号的 所有级别添加到定义列表(步骤632)并且处理继续到步骤636。
如果全局变量不是全局动态对象，则由本发明的机制作出关于全 局变量是否是全局阵列的判定(步骤630)。如果该全局变量是全局 阵列，则本发明机制向定义列表添加索引的引用符号(步骤634)并 且该处理继续到步骤636。否则，该处理也进行到步骤636。
在步骤636中，由本发明的机制作出关于在源程序中是否存在附 加计算的判定。如果存在附加计算，则处理返回到步骤620以检索 下一个计算。否则，之后处理结束。
接下来转向图6D，即根据本发明的优选实施例描述了用于确定 一个计算能否映射到较小的数据类型的简单装载的处理的流程图。 该处理更加详细的描述图6C中步骤624。如图6D所描述的，当本 发明的机制确定一个表达式中的所有引用变量的值能否确定在范围 中时，处理开始(步骤640)。本发明的机制通过使用静态程序数据 流分析或运行时间配置文件执行过程间的范围分析来收集全局对象 的范围信息。
如果表达式的所有引用变量的值能够确定是在范围中，则较小的 数据类型能够用来存储计算值的范围并且该处理继续到步骤 650。否则，本发明的机制确定该计算是否将包含全局动态对象或者 全局阵列的表达式的类型和精度变为较小的数据类型，其为一个转 换表达式(步骤642)。转换表达式将变量的数据类型变为一个较小 的数据类型，例如将双精度型变为整数型。转换表达式可以被缩减 到转换的类型的大小。如果该表达式是将表达式的类型变为较小的 数据类型的转换表达式，则该表达式可以是对象压缩的候选并且该 处理继续到步骤650。
然而，如果该表达式不是将表达式的类型变为较小的数据类型的 转换表达式，则本发明的机制确定该表达式是否是比较表达式(步 骤644)。比较表达式是估计为值0或1的表达式。比较表达式可以 依据结构将全局对象的大小缩减到单个位或字节。
如果该表达式是比较表达式，则处理继续到步骤650。否则，本 发明的机制确定该表达式是否没有以其他方式用于同一循环或其控 制流区域(步骤646)。在这种情况下，该表达式是自包含的。如果 该表达式没有以其他方式用于同一循环或其控制流区域，则该处理 继续到步骤650。否则，之后处理结束。
在步骤650中，该表达式被识别为潜在候选并且能够映射到一个 较小大小的数据类型的简单加载且之后处理结束。
现在转向图7A，即根据本发明的优选实施例描述了用于分析收 集的信息的处理的流程图。该处理更加详细地描述了图5中的步骤 506。如图7A所描述的，当本发明的机制分析使用由图6B，6C和 6D中的处理所产生的使用列表和定义列表时，处理开始(步骤702)。 接着，本发明的机制使用完成的别名信息来改进候选全局对象(步 骤704)。
一旦改进了候选全局对象，本发明的机制就使用成本分析选择候 选计算(步骤706)。一旦选择了候选计算，本发明的机制就对于候 选计算产生新的全局变量(步骤708)。产生的新的全局变量包括基 础符号和间接或索引的引用符号。之后该处理结束。
现在转向图7B，即根据本发明的优选实施例描述了用于根据成 本分析为强度缩量选择候选计算并且对该候选计算产生全局变量的 处理的流程图。该处理更加详细地描述了图7A中的步骤704和706。 如图7B所描述的，当本发明的机制在使用列表中定位下一个项时， 处理开始(步骤708)。接着，本发明的机制选择被树状计算引用的 全局变量(步骤710)并且从与引用的全局变量相对应的定义列表得 到执行成本(步骤712)。对于流不敏感分析，该执行成本可以是执 行计数。对于流敏感分析，该执行成本可以是为各个全局变量存储 指定的加权。根据从控制流和数据流分析中获得的达到定义和达到 的使用信息来确定该加权。
在获得执行成本之后，本发明的机制比较树状计算引用的全局变 量的执行计数(步骤714)并且确定该树状计算是否是预计算优化的 候选(步骤716)。该步骤包括确定该计算的预计算的总成本是否比 当前计算成本低很多。
如果该树状计算是预计算优化的候选，则本发明的机制确定在该 计算中引用的全局变量是否有很大的大小(步骤718)。如果该全局 变量的大小为大，则本发明的机制对于产生该计算的新全局符号(步 骤720)和该计算中的间接或索引的引用的每个级别的新的全局符号 (步骤722)。产生该符号之后，本发明的机制将该符号添加到使用 列表(步骤724)。然后该处理继续到步骤730。
转回到步骤718，如果该全局对象大小不大，则本发明的机制确 定该树状计算是否包括任何子计算(步骤726)。如果存在子计算， 则本发明的机制将该子计算添加到使用列表(步骤728)并且返回到 步骤710以进一步分析该子计算。如果不存在子计算，则该处理继 续到步骤730。
在步骤730中，本发明的机制确定在使用列表中是否存在附加 项。如果存在附加项，则该处理返回到步骤708以获得下一个项。 否则，之后处理结束。
现在转向图8A，即根据本发明的优选实施例描述了在逆推法期 间修改代码的中间格式文件的处理的流程图。该处理更加详细地描 述了图5中的步骤508。如图8A所描述的，当本发明的机制以深度 优先顺序或从下到上的顺序遍历由编译器产生的中间格式文件时， 处理开始(步骤802)。
接着，本发明的机制为引用全局变量的每一个计算插入存储操作 (步骤804)。该存储操作被插入到在整个程序中所有的全局变量的 定义点，在这些点上定义了基础符号、其间接或索引的引用符号或 其别名符号。最后，本发明的机制用新的全局动态对象的间接引用 或新的全局阵列的索引引用来代替候选计算(步骤806)。之后处理 结束。
现在转向图8B，即根据本发明的优选实施例描述了对于引用全 局变量的每个计算插入存储操作的处理的流程图。该处理更加详细 地描述了图8A中的步骤804。如图8B所描述的，当本发明的机制 对候选计算所引用的下一个全局变量进行定位时，处理开始(步骤 808)。
接着，本发明的机制确定候选计算是否是对动态对象或阵列的间 接或索引的引用的最高级别的存储操作(步骤814)。如果该候选计 算是对间接或索引的引用的最高级别的存储操作，则本发明的机制 插入该计算的间接或索引的引用值的最高级别的存储操作(步骤 816)。之后处理继续到步骤830。
如果该候选计算不是间接或索引的引用的最高级别的存储操作， 则本发明的机制继续确定该候选计算是否是对于动态对象的间接引 用的第二高级别的存储分配(步骤818)。如果该候选计算是动态对 象的间接引用的第二高级别的存储分配，则本发明的机制插入一个 存储操作以对具有较小大小的新的动态对象的间接引用的第二高级 别进行分配存储(步骤820)。如果该间接引用的最高级别是1，则 该间接引用的第二高级别是基础指针。之后处理继续到步骤830。
返回到步骤818，如果该候选计算不是对于动态对象的间接引用 的第二高级别的存储分配，则本发明的机制确定该候选计算是否是 对于动态对象的间接引用指针的基础指针或较低级别的存储分配 (步骤822)。
如果该候选计算是对于动态对象的间接引用指针的基础指针或 较低级别的存储分配，本发明的机制就插入一个存储操作以对具有 同样大小的新的动态对象的间接引用指针的基础指针或较低级别分 配存储(步骤824)。之后处理继续到步骤830。
否则，本发明的机制确定该候选计算是否是动态对象的指针赋值 (步骤826)。如果该候选计算是动态对象的指针赋值，则本发明的 机制通过用新的全局变量和其相应的别名符号代替整个赋值语句来 向该新的全局变量插入存储操作(步骤828)。之后该处理继续到步 骤830。如果该候选计算不是指针赋值，则该处理也继续到步骤830。
在步骤830中，本发明的机制确定附加的全局变量是否由候选计 算引用。如果附加全局变量由候选计算引用，则处理返回步骤808 以定位由候选计算引用的下一个全局变量。否则这之后该处理结束。
现在转到图9，即说明了根据本发明的优选实施例描述了使用过 程间的强度缩量在优化之前的示例性软件程序的示意图。如图9所 描述的，在该示例性实施例中，源程序900包括变量声明902，bar 过程904和foo过程906。
变量声明902包括两个声明，变量“a”和“b”的声明。变量“a” 是类型指针到浮点指针的全局动态对象。变量“b”是M×N维的二 维整数阵列。
Bar过程904包括变量“a”的存储操作908，其向变量“a”分 配大小为M个浮点指针的存储。Bar过程904还包括动态阵列“a[i]” 的存储操作910，其向变量a[i]分配大小为N个浮点的存储。
过程foo906包括两个表达式，表达式912和914。表达式912 将Fa(a[i][j])916与1比较。Fa916是包括引用a的表达式。表达 式914是按模计算表达式，其将Fb(b[i][j])918对于256求模以将 Fb918的值转换为字节的大小。
在正推法期间，本发明的机制不仅收集基础全局对象的信息还收 集其间接或索引的引用的级别。在该例中，定义列表包括对基础符 号a、间接引用的第二高级a[]、间接引用的第一高级a[][]以及索引 引用b[][]的项。也记录了对象的基础符号与其间接或索引的引用之 间的关系。
另一方面，使用列表包括树状表达式912和914的项。表达式 912被添加到使用列表，这是因为Fa916是比较表达式并且被本发明 的机制识别为对象压缩的候选。表达式914也被添加到使用列表， 这是因为Fb918将一个值转换成比整型的大小小的字节的大小。因 此，表达式914也被识别为对象压缩的候选。当该表达式被记录在 使用列表中时，就从存储在使用列表中的项中排除所记录的表达式 的索引信息。
在正推法期间收集定义和使用信息后，本发明的机制根据成本分 析来分析该信息并且选择出对强度缩量的候选计算。如果一个计算 的预计算的总成本远低于当前计算的成本，则选择该计算为优化的 候选。在该例子中，如果确定变量“a”和“b”大小为大并且其执 行计数远高于其定义的执行计数，则选择表达式912和914为优化 的候选计算。
然后本发明的机制产生对两个选择的计算的新的全局变量。产生 的全局变量的数目依赖于该计算中其间接的或索引的引用的级别的 数目。在该例中，对全局变量“a”产生的新的全局变量是isra，对 应于间接引用a[]的第二高级的是isra[]，而对应于间接引用a[][]的第 一高级的是isra[][]。相似地，也对于全局变量b产生isrb和isrb[][]。
在产生新的全局变量之后，本发明的机制对于每一个选择的引用 这两个全局变量的计算插入存储操作。本发明的机制以从下到上的 顺序或以深度优先的顺序遍历调用图。
现在转向图10，即说明了根据本发明的优选实施例描述的使用 程序间的强度缩量的优化之后的示例性软件程序的图。如图10所描 述的，在本示例性实施中，优化的程序1000类似于图9中的源程序 900，其包括声明1002，bar过程1004和foo过程1006。然而，本 发明的机制对于在声明1002中声明的每一个变量在bar过程1004 中插入两个存储操作。
在声明1002中声明的变量中的一个是声明1008或“bool**isra”， 用类型指针到布尔指针声明了所创建的变量“a”的新的全局变量。 如图9所述，由于Fa是能够缩减到1比特或1字节的大小的比较表 达式，所以表达式912能够缩减到布尔表达式。
在声明1002中声明的另一个变量是声明1010或“char isrb[M][N]”，用字符型和M×N维声明所创建的变量“b”新的全 局阵列。如图9所述，因为表达式914将Fb的值转换为一字节的大 小以及同样具有一字节大小的字符型，所以能够通过使用较小的数 据类型优化表达式914。
Bar过程1004包括两个插入的存储操作1014和1016。操作1014 向新的全局变量“isra”分配具有M个布尔指针大小的存储。插入第 二个插入的存储操作，操作1016，以向新的全局符号产生的“isra[]” 分配具有N个布尔指针大小的存储。操作1016以较小的大小分配存 储，这是因为isra[]是变量a的间接引用的第二高级。
在插入存储操作之后，本发明的机制用新的全局对象的间接引用 或新的全局阵列的索引引用来代替所选的候选计算。在这个例子中， 图9中的表达式912以isra[i][j]来代替，其为变量“a”的间接引用 的最高级，并且表达式914以isrb[i][j]来代替，其为变量“b”的索 引引用。
现在转向图11，即说明了根据本发明的优选实施例所描述的使 用程序间的强度缩量的进一步优化之后的示例性软件程序的图。如 图11所描述的，程序1100类似于图10中优化的程序1000，除了foo 过程1102被进一步优化，去掉了if分支语句。
总之，本发明提供一种使用全局对象的程序间的强度缩量来改善 数据高速缓存的性能的方法、设备和计算机指令。当一个程序中的 计算改变且以新的全局变量的间接或索引的引用来替代该循环中的 计算时，本发明产生并更新全局变量。以此方式，过程间地分析全 局变量的使用方式并且将全局对象重新映射到较小大小的对象，这 样就可以产生高速缓存效率更高的程序并且改善数据高速缓存的性 能。
很重要的是注意到当在全功能数据处理系统的情景下描述本发 明时，本领域普通技术人员将理解本发明的处理能够以指令的计算 机可读介质的形式和多种形式来分布，并且不管实际用于执行该分 布的信号承载介质的具体类型本发明都同样地适用。计算机可读介 质的例子包括例如软盘、硬盘驱动器、RAM、CD-ROM、DVD-ROM 的可再次记录型的介质以及例如数字和模拟通信链接、使用了例如 射频和光波传输的传输形式的有线或无线通信链接的传输类型媒 体。该计算机可读介质可以采用编码格式的形式，其在具体的数据 处理系统中被解码以供实际使用。
本发明的描述是为了解释和说明的目的，而没有意图用本发明所 公开的形式来穷尽或是限制发明。很多的修改和变形对于本领域普 通技术人员是显而易见的。实施例的选择和描述是为了最好地解释 本发明的原理，实际应用，并且可以使本技术领域的其他普通技术 人员理解本发明的适用于预期的具体使用的具有各种修改的各种实 施例。
相关申请的交叉引用
本发明涉及名为“使用过程间强度缩量优化软件程序的方法和设 备”的申请，代理案号为CA920040084US1，其与本申请同时提交， 转让与同一受让人，且通过参考引入本申请。
在所描述的例子中，服务器104与存储单元106一起连接到网络 102。另外，客户108，110和112连接到网络102上。这些客户108、 110和112可以是，例如，个人计算机或网络计算机。在所描述的例 子中，服务器104提供例如引导文件、操作系统图像和应用程序的 数据到客户108-112。客户108、110和112是服务器104的客户。 网络数据处理系统100可以包括未示出的附加的服务器、客户及其 他设备。在所描述的例子中，网络数据处理系统100是具有代表着 全球网络和网关，并使用传输控制协议/互联网协议(TCP/IP)协议 组进行互相通信的网络102的互联网。互联网的中心是主节点或主 计算机之间的高速数据通信线的中枢，这些主节点或主计算机由成 千上万个发送数据和信息的商业的、政府的、教育的以及其他的计 算机系统组成。当然，网络数据处理系统100也可以由多个不同类 型的例如内联网、局域网(LAN)或广域网(WAN)的网络来实现。 图1意图作为例子而不是作为本发明的结构限制。
参考图2，根据本发明的优选实施例描述了其能够实现为例如图 1中的服务器104的服务器的数据处理系统的方框图。数据处理系统 200可以是对称多处理器(SMP)系统，该系统包括连接到系统总线 206的多个处理器202和204。可选择地，可以使用单个处理器系统。 存储控制器/高速缓存208也连接到系统总线206，208提供到本地存 储器209的接口。I/O总线桥接器210连接到系统总线206并且提供 到I/O总线212的接口。存储控制器/高速缓存208和I/O总线桥接 器210可以如描述的那样集成在一起。
连接到I/O总线212的外围部件互连(PCI)总线桥接器214提 供到PCI本地总线216的接口。多个调制解调器可以连接到PCI本 地总线216。典型的PCI总线的实现将支持四个PCI扩展槽或附加连 接器。图1中到客户108-112的通信链路可通过调制解调器218和通 过附加连接器连接到PCI本地总线216的网络适配器220来提供。
附加的PCI总线桥接器222和224向附加的PCI本地总线226 和228提供接口，通过其可以支持附加的调制解调器或网络适配器。 以这种方式，数据处理系统200允许到多网络计算机的连接。如图 所示存储器映射图形适配器230和硬盘232也可以直接或间接地连 接到I/O总线212。
本领域普通技术人员将理解图2中描述的硬件可以变化。例如， 例如光盘驱动器等的外围设备也可以附加于或代替所述的硬件来使 用。所述例子不意味着对于本发明的结构限制。
图2中描述的数据处理系统可以是例如IBM eServerTM 系统，该系统是位于纽约阿蒙德的美国国际商用机器公司的产品， 运行着高级交互执行程序操作系统或LINUXTM操作系统。
IBM，eServer，Pseries和AIX是美国国际商用机器公司的商标或 注册商标。LINUX是Linus Torvalds的商标。
现在参考图3，其为描述了可以实施本发明的数据处理系统的方 框图。数据处理系统300是客户计算机的例子。数据处理系统300 采用外围部件互连(PCI)本地总线结构。虽然所述的例子采用了PCI 总线，但是也可以使用例如图形加速端口(AGP)和工业标准结构 (ISA)的其他总线结构。处理器302和主存储器304通过PCI桥接 器308连接到PCI本地总线306。PCI桥接器308也可以包括对于处 理器302的集成存储控制器和高速缓存。通过直接元件互连或通过 附加板可以形成到PCI本地总线306的附加连接。在所述的例子中， 局域网(LAN)适配器310、SCSI主机总线适配器312和扩展总线 接口314通过直接元件连接而连接到PCI本地总线306。相反，音频 适配器316、图形适配器318以及音频/视频适配器319通过插入到 扩展槽的附加板而连接到PCI本地总线306。扩展总线接口314为键 盘和鼠标适配器320、调制解调器322和附加的存储器324提供连接。 小型计算机系统接口(SCSI)主机总线适配器312为硬盘驱动器326、 磁带驱动器328和CD-ROM驱动器330提供连接。典型的PCI本地 总线的实现将支持三或四个PCI扩展槽或附加连接器。
操作系统运行在处理器302上并且用于对图3中的数据处理系统 300内的各种元件进行协调并提供控制。该操作系统可以是商用的操 作系统，例如从微软公司可得到的WindowsTM XP。Windows是微软 公司的商标。例如Java的面向对象的程序设计系统可以与操作系统 一起运行并且从在数据处理系统300上执行的Java程序或应用向操 作系统提供调用。“Java”是Sun微系统公司的商标。操作系统、面 向对象的程序设计系统以及应用程序或程序的指令位于例如硬盘驱 动器326的存储设备上并且可以装载进主存储器304中由处理器302 执行。
本领域技术人员将理解图3中的硬件可以依据实现方式而变化。 其他的内部硬件或外围设备，例如闪速只读存储器ROM，等效非易 失性存储器或光盘驱动器等，可以附加于或代替图3中描述的硬件 来使用。而且，本发明的处理可以应用于多处理器数据处理系统。
作为另外一个例子，数据处理系统300可以为独立系统，该独立 系统配置为可引导的，而不依赖于某种类型的网络通信接口。作为 又一个例子，数据处理系统300可以是个人数字助理(PDA)设备， 其配置有ROM和/或闪速ROM以提供存储操作系统文件和/或用户 产生的数据的非易失性存储器。
图3中描述的例子和上述例子不意味着暗示结构的限制。例如， 数据处理系统300除了采取PDA形式也可以是笔记本电脑或手提电 脑。数据处理系统300也可以是公共咨讯站或网络设备(Web appliance)。
本发明提供了一种使用全局对象的过程间强度缩量来改善数据 高速缓存的性能的方法、设备以及计算机指令。本发明的机制通过 压缩或预计算全局对象来减少在软件程序循环中重复引用的全局对 象的大小。全局对象包括全局动态对象和全局阵列。
对象压缩减小了高速缓存在热点的消耗并且提高了有效高速缓 存的块大小以及有效高速缓存容量。预计算通过利用处理器专用硬 件减少了在强度上的计算成本。
本发明的机制执行二重分析。该二重分析包括在正推法程序中遍 历软件程序的中间格式文件以收集信息。中间格式文件包括调用图、 控制流图和数据流图。也可以使用其它类型的中间格式文件。
在正推法期间，本发明的机制以逆深度优先顺序或从上到下的顺 序遍历调用图以收集软件程序中全局变量的定义和使用该信息。定 义信息保留了在程序中存储所有全局变量的痕迹。使用信息保留了 作为成本预算的候选的高成本计算的痕迹。
另外，本发明的机制使用转义分析来分析全局对象的别名，并且 识别对于对象压缩或预算的候选全局对象。转义分析是一种可以用 来确定全局对象的别名，即确定两个全局对象可否涉及存储器中的 同一位置的技术。任何作为自变量或返回值通过的对象由定义进行 转义。当一个对象转义了，这意味着它已经暴露在现有程序的外边 了。如果能确定全局对象的准确别名，则全局对象可以是对象压缩 的候选。使用位矢量列出候选全局对象。在遍历调用图期间改进该 候选列表并且在遍历结束时完成该列表。
当识别出候选全局对象时，本发明的机制向使用列表添加代表引 用全局对象的计算的树状输入。排除全局对象的索引，因为它们可 以在本地变量上操作并且是不需要的。如果在候选计算中引用的全 局变量是全局动态对象，那么除了树形计算，所有级别的间接引用 符号也添加到该使用列表。如果引用的全局变量是全局阵列，本发 明的机制就添加索引的引用符号到定义列表。
一旦识别出候选全局对象并且收集了定义和使用信息，本发明的 机制就在遍历完调用图所有的节点之后在正推法的结尾分析该信 息。该分析包括根据完成的别名信息来完成对于对象压缩或预计算 的全局对象候选，以及根据整个程序的成本分析来识别对于强度缩 量的候选计算。
如果一个计算只包含全局对象则该计算可以确定为对象压缩的 候选，其中引用的全局对象的索引可以包含本地变量。当且仅当一 个候选计算能够映射到大小较小的数据类型的对象的简单装载时， 该计算也可以确定为对象压缩的候选。
关于优化的候选计算，例如，如果预计算的总成本比当前计算成 本低很多，计算的预计算可能为有利。预计算的总成本由两个因素 确定：计算和实现定义的执行量，以及如果全局变量是动态对象或 阵列时，引用的全局变量的总大小。
识别候选计算之后，本发明的机制产生新的全局变量。全局变量 的大小依赖于计算中对于全局变量的间接或索引的引用的级别数。 对于最高级的间接引用的新的全局变量而具有能够根据结构保持计 算的数值范围的大小最小或较小的类型。对于全局变量的别名对象 也产生新的符号。别名对象之间的关系也被记录以用于别名分析。
在产生新的全局变量之后，本发明的机制修改在逆推法期间所编 译代码的中间格式文件。在逆推法期间，本发明的机制以深度优先 顺序或从下到上的顺序遍历中间格式文件的调用图。
本发明的机制通过用新的全局动态对象或阵列的间接的或索引 的引用代替候选计算的所有具体值来修改中间格式文件。关于候选 全局对象，本发明的机制在软件程序中对于每个引用了候选全局对 象的计算向新的全局变量在其所有的定义点插入一个存储操作，在 其定义点处定义了基础符号、间接或索引的引用符号或其别名符号。
这样，本发明提供了过程间的强度缩量方法，该方法改善了数据 高速缓存的性能。本发明预行计算源程序中的预计算的总成本并且 确定计算是否是优选的候选。然后本发明在过程间中以新的全局对 象的间接引用或新的全局阵列的索引的引用来代替候选计算，这样 就减小在软件程序循环中重复引用的全局对象的大小。
现在转向图4，即在本发明的优选实施例中描述了说明源程序、 编译器和机器语言指令之间的关系的方框图。如图4中所说明的， 在这个说明性例子中，例如程序员的用户可以定义源程序400。源程 序400包括变量和过程。
变量可以是全局的或本地的。全局变量可以由源程序400内的任 何过程存取。在本例中，变量a 406定义为浮点型而变量b 407定义 为整型。变量a 406和变量b 407都可由过程foo 408和过程bar 412 存取。在过程中，可能出现本地变量。在本例中，变量i 410在过程 foo408中定义为整型并且只在过程foo 408中可存取。
一旦确定了源程序400，程序员就可以用编译器402编译源程序 400。编译器402可以在例如图2中的数据处理系统200或图3中的 数据处理系统300的数据处理系统中实现。在编译处理中，编译器 402分几个阶段处理源程序400：词法分析阶段414、语法分析阶段 416、中间格式文件阶段418、代码优化阶段420和代码产生阶段422。
词法分析阶段414分析源程序400。在该阶段，编译器402读出 源程序400中的字符并且把它们分组进代表着逻辑内聚的字符串， 例如标识符、操作符和关键词的令牌流中。
语法分析416在令牌串上施加一个层次结构。在语法分析416 期间，编译器402从词法分析414中获得令牌串并且通过进行从上 到下或从下到上的剖析来确定该串是否是源程序的有效结构。
一旦完成了词法分析和语法分析，编译器402产生源程序400 的明确的中间代码418，该代码可以采取各种形式。例如，一个中间 代码可以是调用图、数据流图或控制流图。在优选实施例中，本发 明的机制对由编译器402产生的调用图进行二重遍历。然而，也可 以使用其它中间格式文件。
在编码优化阶段420中，编译器402进行各种转换以改善中间编 码。这些转换包括例如循环分片或条状开采的循环转换。这些转换 改善了目标机器代码的性能。
最后，编译器402通过对程序使用的每个变量选择存储位置产生 目标机器代码。每个中间指令被翻译成机器语言指令串，例如执行 同一任务的机器语言指令404。机器语言指令404可以用于例如 平台的具体平台。UNIX是Open Group的注册商标。然后程 序员可以以改善的性能在具体平台上执行这些指令。
现在转向图5，即根据本发明的优选实施例描述了使用内部程序 的强度缩量来优化软件程序的处理的流程图。当如图4的编译器402 的编译器产生一个源程序的中间代码时处理开始(步骤502)。产生 的中间格式文件可以是调用图、控制流图或数据流图。
接着，本发明的机制在正推法期间收集包括全局变量的使用和定 义信息的信息(步骤504)。正推法是以逆深度优先或从上到下的顺 序遍历调用图。一旦收集了信息，本发明的机制就在遍历完调用图 的所有节点之后在正推法结束时分析收集的信息(步骤506)。
最后，本发明的机制在逆推法期间修改编译代码的中间格式文件 (步骤508)。逆推法是以深度优先或从下到上的顺序遍历调用图。 其后处理结束。通过使用二重分析，通过增加更新标记有每个程序 最小计算数目的引用而避免了冗余计算。
现在转向图6A，即描述了根据本发明的优选实施例的在正推法 期间收集信息的处理的流程图。该处理更加详细地描述了图5中的 步骤504。如图6A所描述的，当本发明的机制以深度优先顺序或从 上到下的顺序遍历由编译器产生的中间格式文件时，处理开始了(步 骤602)。
接着，本发明的机制使用全局对象的过程间别名分析来识别候选 全局对象(步骤604)。在识别了候选全局对象之后本发明的机制收 集对全局对象的存储操作和全局对象的计算(步骤606)。全局对象 的计算收集在使用列表中并且对全局对象的存储操作收集在定义列 表中。一旦产生使用列表和定义列表，之后该处理结束。
现在转向图6B，即根据本发明的优选实施例描述了使用过程间 的别名分析来识别候选全局对象的处理的流程图。该处理更加详细 地描述了图6A中步骤604的处理。如图6B所描述的，当本发明的 机制排除了可以在未定义的程序中修改的全局变量时，处理开始(步 骤608)。
定义的程序是具有相应的中间格式文件的程序。如果一个程序的 中间格式文件是不可得的，则该程序被识别为未定义程序。一个未 定义程序的例子包括将汇编代码链接到编译代码的程序。未定义程 序中的全局变量被排除，这是因为在这样的程序中不可能进行预计 算。
接着，本发明的机制使用转义分析来分析全局动态对象和阵列的 别名(步骤610)。可以确定别名的全局对象可以作为候选。然后， 本发明的机制分析全局动态对象和阵列的大小(步骤612)。全局对 象或阵列的大小可以通过静态程序数据流分析或运行时间配置文件 而得到。大小大的全局对象可以为候选。最后，由本发明的机制建 立候选全局对象的列表(步骤614)并且其后处理结束。
下面转向图6C，即根据本发明的优选实施例描述了用于收集对 于全局对象的存储操作和全局对象的计算的处理的流程图。该处理 更加详细地描述了图6A中的步骤606。
如图6C所描述的，当本发明的机制定位于下一个计算时，处理 开始(步骤620)。接着，本发明的机制确定该计算是否只包含全局 变量(步骤622)。在这种情况下，所引用的全局变量的索引可以包 含本地变量。如果该计算不只包含全局变量，则该计算可能不是潜 在的候选并且处理继续到步骤636。
如果该计算只包含全局变量，则本发明的机制确定该计算能否映 射到一个大小较小的数据类型的简单装载(步骤624)。该步骤在图 6D中更详细的进行了说明。如果该计算不能映射到一个大小较小的 数据类型的简单装载，则处理继续到步骤636。如果该计算能映射到 一个大小较小的数据类型的简单装载，则本发明的机制向使用列表 添加代表排除索引的计算的树(步骤626)，因为该索引是不需要的。
在添加了代表计算的树之后，本发明的机制确定在本计算中引用 的全局变量是否是全局动态对象(步骤628)。如果该全局变量是全 局动态对象，则本发明的机制不只将基础对象还将间接引用符号的 所有级别添加到定义列表(步骤632)并且处理继续到步骤636。
如果全局变量不是全局动态对象，则由本发明的机制作出关于全 局变量是否是全局阵列的判定(步骤630)。如果该全局变量是全局 阵列，则本发明机制向定义列表添加索引的引用符号(步骤634)并 且该处理继续到步骤636。否则，该处理也进行到步骤636。
在步骤636中，由本发明的机制作出关于在源程序中是否存在附 加计算的判定。如果存在附加计算，则处理返回到步骤620以检索 下一个计算。否则，之后处理结束。
接下来转向图6D，即根据本发明的优选实施例描述了用于确定 一个计算能否映射到较小的数据类型的简单装载的处理的流程图。 该处理更加详细的描述图6C中步骤624。如图6D所描述的，当本 发明的机制确定一个表达式中的所有引用变量的值能否确定在范围 中时，处理开始(步骤640)。本发明的机制通过使用静态程序数据 流分析或运行时间配置文件执行过程间的范围分析来收集全局对象 的范围信息。
如果表达式的所有引用变量的值能够确定是在范围中，则较小的 数据类型能够用来存储计算值的范围并且该处理继续到步骤 650。否则，本发明的机制确定该计算是否将包含全局动态对象或者 全局阵列的表达式的类型和精度变为较小的数据类型，其为一个转 换表达式(步骤642)。转换表达式将变量的数据类型变为一个较小 的数据类型，例如将双精度型变为整数型。转换表达式可以被缩减 到转换的类型的大小。如果该表达式是将表达式的类型变为较小的 数据类型的转换表达式，则该表达式可以是对象压缩的候选并且该 处理继续到步骤650。
然而，如果该表达式不是将表达式的类型变为较小的数据类型的 转换表达式，则本发明的机制确定该表达式是否是比较表达式(步 骤644)。比较表达式是估计为值0或1的表达式。比较表达式可以 依据结构将全局对象的大小缩减到单个位或字节。
如果该表达式是比较表达式，则处理继续到步骤650。否则，本 发明的机制确定该表达式是否没有以其他方式用于同一循环或其控 制流区域(步骤646)。在这种情况下，该表达式是自包含的。如果 该表达式没有以其他方式用于同一循环或其控制流区域，则该处理 继续到步骤650。否则，之后处理结束。
在步骤650中，该表达式被识别为潜在候选并且能够映射到一个 较小大小的数据类型的简单加载且之后处理结束。
现在转向图7A，即根据本发明的优选实施例描述了用于分析收 集的信息的处理的流程图。该处理更加详细地描述了图5中的步骤 506。如图7A所描述的，当本发明的机制分析使用由图6B，6C和 6D中的处理所产生的使用列表和定义列表时，处理开始(步骤702)。 接着，本发明的机制使用完成的别名信息来改进候选全局对象(步 骤704)。
一旦改进了候选全局对象，本发明的机制就使用成本分析选择候 选计算(步骤706)。一旦选择了候选计算，本发明的机制就对于候 选计算产生新的全局变量(步骤708)。产生的新的全局变量包括基 础符号和间接或索引的引用符号。之后该处理结束。
现在转向图7B，即根据本发明的优选实施例描述了用于根据成 本分析为强度缩量选择候选计算并且对该候选计算产生全局变量的 处理的流程图。该处理更加详细地描述了图7A中的步骤704和706。 如图7B所描述的，当本发明的机制在使用列表中定位下一个项时， 处理开始(步骤708)。接着，本发明的机制选择被树状计算引用的 全局变量(步骤710)并且从与引用的全局变量相对应的定义列表得 到执行成本(步骤712)。对于流不敏感分析，该执行成本可以是执 行计数。对于流敏感分析，该执行成本可以是为各个全局变量存储 指定的加权。根据从控制流和数据流分析中获得的达到定义和达到 的使用信息来确定该加权。
在获得执行成本之后，本发明的机制比较树状计算引用的全局变 量的执行计数(步骤714)并且确定该树状计算是否是预计算优化的 候选(步骤716)。该步骤包括确定该计算的预计算的总成本是否比 当前计算成本低很多。
如果该树状计算是预计算优化的候选，则本发明的机制确定在该 计算中引用的全局变量是否有很大的大小(步骤718)。如果该全局 变量的大小为大，则本发明的机制对于产生该计算的新全局符号(步 骤720)和该计算中的间接或索引的引用的每个级别的新的全局符号 (步骤722)。产生该符号之后，本发明的机制将该符号添加到使用 列表(步骤724)。然后该处理继续到步骤730。
转回到步骤718，如果该全局对象大小不大，则本发明的机制确 定该树状计算是否包括任何子计算(步骤726)。如果存在子计算， 则本发明的机制将该子计算添加到使用列表(步骤728)并且返回到 步骤710以进一步分析该子计算。如果不存在子计算，则该处理继 续到步骤730。
在步骤730中，本发明的机制确定在使用列表中是否存在附加 项。如果存在附加项，则该处理返回到步骤708以获得下一个项。 否则，之后处理结束。
现在转向图8A，即根据本发明的优选实施例描述了在逆推法期 间修改代码的中间格式文件的处理的流程图。该处理更加详细地描 述了图5中的步骤508。如图8A所描述的，当本发明的机制以深度 优先顺序或从下到上的顺序遍历由编译器产生的中间格式文件时， 处理开始(步骤802)。
接着，本发明的机制为引用全局变量的每一个计算插入存储操作 (步骤804)。该存储操作被插入到在整个程序中所有的全局变量的 定义点，在这些点上定义了基础符号、其间接或索引的引用符号或 其别名符号。最后，本发明的机制用新的全局动态对象的间接引用 或新的全局阵列的索引引用来代替候选计算(步骤806)。之后处理 结束。
现在转向图8B，即根据本发明的优选实施例描述了对于引用全 局变量的每个计算插入存储操作的处理的流程图。该处理更加详细 地描述了图8A中的步骤804。如图8B所描述的，当本发明的机制 对候选计算所引用的下一个全局变量进行定位时，处理开始(步骤 808)。
接着，本发明的机制确定候选计算是否是对动态对象或阵列的间 接或索引的引用的最高级别的存储操作(步骤814)。如果该候选计 算是对间接或索引的引用的最高级别的存储操作，则本发明的机制 插入该计算的间接或索引的引用值的最高级别的存储操作(步骤 816)。之后处理继续到步骤830。
如果该候选计算不是间接或索引的引用的最高级别的存储操作， 则本发明的机制继续确定该候选计算是否是对于动态对象的间接引 用的第二高级别的存储分配(步骤818)。如果该候选计算是动态对 象的间接引用的第二高级别的存储分配，则本发明的机制插入一个 存储操作以对具有较小大小的新的动态对象的间接引用的第二高级 别进行分配存储(步骤820)。如果该间接引用的最高级别是1，则 该间接引用的第二高级别是基础指针。之后处理继续到步骤830。
返回到步骤818，如果该候选计算不是对于动态对象的间接引用 的第二高级别的存储分配，则本发明的机制确定该候选计算是否是 对于动态对象的间接引用指针的基础指针或较低级别的存储分配 (步骤822)。
如果该候选计算是对于动态对象的间接引用指针的基础指针或 较低级别的存储分配，本发明的机制就插入一个存储操作以对具有 同样大小的新的动态对象的间接引用指针的基础指针或较低级别分 配存储(步骤824)。之后处理继续到步骤830。
否则，本发明的机制确定该候选计算是否是动态对象的指针赋值 (步骤826)。如果该候选计算是动态对象的指针赋值，则本发明的 机制通过用新的全局变量和其相应的别名符号代替整个赋值语句来 向该新的全局变量插入存储操作(步骤828)。之后该处理继续到步 骤830。如果该候选计算不是指针赋值，则该处理也继续到步骤830。
在步骤830中，本发明的机制确定附加的全局变量是否由候选计 算引用。如果附加全局变量由候选计算引用，则处理返回步骤808 以定位由候选计算引用的下一个全局变量。否则这之后该处理结束。
现在转到图9，即说明了根据本发明的优选实施例描述了使用过 程间的强度缩量在优化之前的示例性软件程序的示意图。如图9所 描述的，在该示例性实施例中，源程序900包括变量声明902，bar 过程904和foo过程906。
变量声明902包括两个声明，变量“a”和“b”的声明。变量“a” 是类型指针到浮点指针的全局动态对象。变量“b”是M×N维的二 维整数阵列。
Bar过程904包括变量“a”的存储操作908，其向变量“a”分 配大小为M个浮点指针的存储。Bar过程904还包括动态阵列“a[i]” 的存储操作910，其向变量a[i]分配大小为N个浮点的存储。
过程foo906包括两个表达式，表达式912和914。表达式912 将Fa(a[i][j])916与1比较。Fa916是包括引用a的表达式。表达 式914是按模计算表达式，其将Fb(b[i][j])918对于256求模以将 Fb918的值转换为字节的大小。
在正推法期间，本发明的机制不仅收集基础全局对象的信息还收 集其间接或索引的引用的级别。在该例中，定义列表包括对基础符 号a、间接引用的第二高级a[]、间接引用的第一高级a[][]以及索引 引用b[][]的项。也记录了对象的基础符号与其间接或索引的引用之 间的关系。
另一方面，使用列表包括树状表达式912和914的项。表达式 912被添加到使用列表，这是因为Fa916是比较表达式并且被本发明 的机制识别为对象压缩的候选。表达式914也被添加到使用列表， 这是因为Fb918将一个值转换成比整型的大小小的字节的大小。因 此，表达式914也被识别为对象压缩的候选。当该表达式被记录在 使用列表中时，就从存储在使用列表中的项中排除所记录的表达式 的索引信息。
在正推法期间收集定义和使用信息后，本发明的机制根据成本分 析来分析该信息并且选择出对强度缩量的候选计算。如果一个计算 的预计算的总成本远低于当前计算的成本，则选择该计算为优化的 候选。在该例子中，如果确定变量“a”和“b”大小为大并且其执 行计数远高于其定义的执行计数，则选择表达式912和914为优化 的候选计算。
然后本发明的机制产生对两个选择的计算的新的全局变量。产生 的全局变量的数目依赖于该计算中其间接的或索引的引用的级别的 数目。在该例中，对全局变量“a”产生的新的全局变量是isra，对 应于间接引用a[]的第二高级的是isra[]，而对应于间接引用a[][]的第 一高级的是isra[][]。相似地，也对于全局变量b产生isrb和isrb[][]。
在产生新的全局变量之后，本发明的机制对于每一个选择的引用 这两个全局变量的计算插入存储操作。本发明的机制以从下到上的 顺序或以深度优先的顺序遍历调用图。
现在转向图10，即说明了根据本发明的优选实施例描述的使用 程序间的强度缩量的优化之后的示例性软件程序的图。如图10所描 述的，在本示例性实施中，优化的程序1000类似于图9中的源程序 900，其包括声明1002，bar过程1004和foo过程1006。然而，本 发明的机制对于在声明1002中声明的每一个变量在bar过程1004 中插入两个存储操作。
在声明1002中声明的变量中的一个是声明1008或“bool**isra”， 用类型指针到布尔指针声明了所创建的变量“a”的新的全局变量。 如图9所述，由于Fa是能够缩减到1比特或1字节的大小的比较表 达式，所以表达式912能够缩减到布尔表达式。
在声明1002中声明的另一个变量是声明1010或“char isrb[M][N]”，用字符型和M×N维声明所创建的变量“b”新的全 局阵列。如图9所述，因为表达式914将Fb的值转换为一字节的大 小以及同样具有一字节大小的字符型，所以能够通过使用较小的数 据类型优化表达式914。
Bar过程1004包括两个插入的存储操作1014和1016。操作1014 向新的全局变量“isra”分配具有M个布尔指针大小的存储。插入第 二个插入的存储操作，操作1016，以向新的全局符号产生的“isra[]” 分配具有N个布尔指针大小的存储。操作1016以较小的大小分配存 储，这是因为isra[]是变量a的间接引用的第二高级。
在插入存储操作之后，本发明的机制用新的全局对象的间接引用 或新的全局阵列的索引引用来代替所选的候选计算。在这个例子中， 图9中的表达式912以isra[i][j]来代替，其为变量“a”的间接引用 的最高级，并且表达式914以isrb[i][j]来代替，其为变量“b”的索 引引用。
现在转向图11，即说明了根据本发明的优选实施例所描述的使 用程序间的强度缩量的进一步优化之后的示例性软件程序的图。如 图11所描述的，程序1100类似于图10中优化的程序1000，除了foo 过程1102被进一步优化，去掉了if分支语句。
总之，本发明提供一种使用全局对象的程序间的强度缩量来改善 数据高速缓存的性能的方法、设备和计算机指令。当一个程序中的 计算改变且以新的全局变量的间接或索引的引用来替代该循环中的 计算时，本发明产生并更新全局变量。以此方式，过程间地分析全 局变量的使用方式并且将全局对象重新映射到较小大小的对象，这 样就可以产生高速缓存效率更高的程序并且改善数据高速缓存的性 能。
很重要的是注意到当在全功能数据处理系统的情景下描述本发 明时，本领域普通技术人员将理解本发明的处理能够以指令的计算 机可读介质的形式和多种形式来分布，并且不管实际用于执行该分 布的信号承载介质的具体类型本发明都同样地适用。计算机可读介 质的例子包括例如软盘、硬盘驱动器、RAM、CD-ROM、DVD-ROM 的可再次记录型的介质以及例如数字和模拟通信链接、使用了例如 射频和光波传输的传输形式的有线或无线通信链接的传输类型媒 体。该计算机可读介质可以采用编码格式的形式，其在具体的数据 处理系统中被解码以供实际使用。
本发明的描述是为了解释和说明的目的，而没有意图用本发明所 公开的形式来穷尽或是限制发明。很多的修改和变形对于本领域普 通技术人员是显而易见的。实施例的选择和描述是为了最好地解释 本发明的原理，实际应用，并且可以使本技术领域的其他普通技术 人员理解本发明的适用于预期的具体使用的具有各种修改的各种实 施例。
相关申请的交叉引用
本发明涉及名为“使用过程间强度缩量优化软件程序的方法和设 备”的申请，代理案号为CA920040084US1，其与本申请同时提交， 转让与同一受让人，且通过参考引入本申请。