公开(公告)号：US6026241A

公开(公告)日：2000-02-15

申请号：US873895

申请日：1997-06-13

申请人： Frederick Chow ,  Sun Chan ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Peng Tu

发明人： Frederick Chow ,  Sun Chan ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Peng Tu

IPC分类号： G06F9/45

CPC分类号： G06F8/443

摘要： Partial redundancy elimination of a computer program is described that operates using a static single assignment (SSA) representation of a computer program. The SSA representation of the computer program is processed to eliminate partially redundant expressions in the computer program. This processing involves inserting .PHI. functions for expressions where different values of the expressions reach common points in the computer program. A result of each of the .PHI. functions is stored in a hypothetical variable h. The processing also involves a renaming step where SSA versions are assigned to hypothetical variables h in the computer program, a down safety step of determining whether each .PHI. function in the computer program is down safe, and a will be available step of determining whether each expression in the computer program will be available at each .PHI. function following eventual insertion of code into the computer program for purposes of partial redundancy elimination. The processing also includes a finalize step of transforming the SSA representation of the computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination, and a code motion step of updating the SSA graph based on the insertion information to introduce real temporary variables t for the hypothetical variables h.

摘要翻译： 描述了使用计算机程序的静态单一分配（SSA）表示来操作计算机程序的部分冗余消除。 处理计算机程序的SSA表示以消除计算机程序中的部分冗余表达式。 该处理涉及为表达式插入PHI函数，其中表达式的不同值达到计算机程序中的公共点。 每个PHI函数的结果存储在假设变量h中。 该处理还包括重新命名步骤，其中SSA版本被分配给计算机程序中的假想变量h，确定计算机程序中的每个PHI功能是否下降的安全步骤，以及将是可用的步骤，确定每个表达式 为了部分冗余消除的目的，在计算机程序中将最终将代码插入计算机程序之后，在每个PHI功能中将可用。 该处理还包括将具有假设变量h的计算机程序的SSA表示形式的SSA图形变换为SSA图的最终确定步骤，该SSA图形包括反映最终插入代码到计算机程序中以便部分冗余消除的目的的一些插入信息，以及代码运动步骤 基于插入信息更新SSA图，以为假设变量h引入真实临时变量t。

公开(公告)号：US5768596A

公开(公告)日：1998-06-16

申请号：US636605

申请日：1996-04-23

申请人： Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

发明人： Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

IPC分类号： G06F9/45

CPC分类号： G06F8/443

摘要： A system and method for an optimizer of a compilation suite for representing aliases and indirect memory operations in static single assignment (SSA) during compilation of a program having one or more basic blocks of source code. The optimizer converts all scalar variables of said program to SSA form, wherein said SSA form includes a plurality of variable versions, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the variable versions. The optimizer also determines whether a variable version can be renamed to a zero version, and upon such a determination, the optimizer renames the variable version to a zero version. The optimizer further converts all indirect variables of a program to SSA form, wherein the SSA form includes a plurality of virtual variable versions such that a virtual variable is assigned to an indirect variable, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the virtual variables. The optimizer hashes a unique value number and creates a corresponding hash table entry for each variable version and each virtual variable remaining after renaming all zero versions. The optimizer also applies global value numbering to each basic block of the program.

公开(公告)号：US06571387B1

公开(公告)日：2003-05-27

申请号：US09499745

申请日：2000-02-08

申请人： Frederick Chow ,  Raymond Lo

发明人： Frederick Chow ,  Raymond Lo

IPC分类号： G06F945

CPC分类号： G06F8/443

摘要： A method and computer program product, within an optimizing compiler, for the global minimization of sign-extension and zero-extension operations in generated code during compilation. The method and computer program product allows, for example, 64-bit compilers targeting the Intel IA64 architecture to improve their SPECint benchmarks by reducing the number of sign-extension and zero-extension operations in the global and intra-procedural scope, thus, speeding up the execution of the compiled program.

摘要翻译： 一种优化编译器中的方法和计算机程序产品，用于在编译期间在生成的代码中全局最小化符号扩展和零扩展操作。 该方法和计算机程序产品允许例如针对Intel IA64架构的64位编译器通过减少全局和程序范围内的符号扩展和零扩展操作的数量来改进其SPECint基准，从而加速 执行编译程序。

公开(公告)号：US6131189A

公开(公告)日：2000-10-10

申请号：US979939

申请日：1997-11-26

申请人： Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

发明人： Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

IPC分类号： G06F9/45

CPC分类号： G06F8/443

摘要： A system and method for an optimizer of a compilation suite for representing aliases and indirect memory operations in static single assignment (SSA) during compilation of a program having one or more basic blocks of source code. The optimizer converts all scalar variables of said program to SSA form, wherein said SSA form includes a plurality of variable versions, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the variable versions. The optimizer also determines whether a variable version can be renamed to a zero version, and upon such a determination, the optimizer renames the variable version to a zero version. The optimizer further converts all indirect variables of a program to SSA form, wherein the SSA form includes a plurality of virtual variable versions such that a virtual variable is assigned to an indirect variable, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the virtual variables. The optimizer hashes a unique value number and creates a corresponding hash table entry for each variable version and each virtual variable remaining after renaming all zero versions. The optimizer also applies global value numbering to each basic block of the program.

摘要翻译： 一种编译套件的优化器的系统和方法，用于在具有一个或多个源代码基本块的程序的编译期间，在静态单赋值（SSA）中表示别名和间接存储器操作。 所述优化器将所述程序的所有标量变量转换为SSA形式，其中所述SSA形式包括多个可变版本，零次或多次出现的chi功能，零个或多个phi功能的出现以及零次或多次出现的mu 功能。 为变量版本插入chi函数，phi函数和mu函数。 优化器还确定变量版本是否可以重命名为零版本，并且在这样的确定时，优化器将变量版本重命名为零版本。 优化器进一步将程序的所有间接变量转换为SSA形式，其中SSA形式包括多个虚拟变量版本，使得虚拟变量被分配到间接变量，零个或多个出现的chi函数，零个或多个出现 的phi功能，以及零个或多个mu功能的出现。 为虚拟变量插入chi函数，phi函数和mu函数。 优化器散列唯一的值编号，并为每个变量版本创建相应的哈希表条目，并在重命名所有零版本后剩余的每个虚拟变量。 优化器还对程序的每个基本块应用全局值编号。

公开(公告)号：US06128775A

公开(公告)日：2000-10-03

申请号：US97713

申请日：1998-06-16

申请人： Frederick Chow ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Peng Tu ,  Sun C. Chan

发明人： Frederick Chow ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Peng Tu ,  Sun C. Chan

IPC分类号： G06F9/45

CPC分类号： G06F8/441 ,  G06F8/443

摘要： A method, system, and computer program product for performing register promotion, that optimizes placement of load and store operations of a computer program within a compiler. Based on the observation that the circumstances for promoting a memory location's value to register coincide with situations where the program exhibits partial redundancy between accesses to the memory location, the system is an approach to register promotion that models the optimization as two separate problems: (1) the partial redundancy elimination (PRE) of loads and (2) the PRE of stores. Both of these problems are solved through a sparse approach to PRE. The static single assignment PRE (SSAPRE) method for eliminating partial redundancy using a sparse SSA representation representations the foundation in eliminating redundancy among memory accesses, enabling the achievement of both computational and live range optimality in register promotion results. A static single use (SSU) representation is defined allowing the dual of the SSAPRE algorithm, called SSUPRE, to perform the partial redundancy elimination of stores. SSUPRE is performed after the PRE of loads, taking advantage of the loads' having been converted into pseudo-register references so that there are fewer barriers to the movement of stores. Consequently, the compiler produces more efficient, register-promoted executable program code from the SSA representation.

摘要翻译： 一种用于执行注册促进的方法，系统和计算机程序产品，其优化了编译器内的计算机程序的加载和存储操作的布局。 基于这样一种观察，即为了提升存储器位置的寄存器值的情况与存储单元存取位置之间存在部分冗余的情况相一致，系统是将优化模型化为两个独立问题的注册升级方法：（1 ）负载的部分冗余消除（PRE）和（2）存储的PRE。 这两个问题都是通过稀疏的PRE方法解决的。 使用稀疏SSA表示消除部分冗余的静态单分配PRE（SSAPRE）方法表示在消除存储器访问之间的冗余的基础上，使得能够在注册促进结果中实现计算和实时范围最优化。 定义了静态单用（SSU）表示，允许称为SSUPRE的SSAPRE算法的双重性来执行商店的部分冗余消除。 SSUPRE在负载的PRE之后执行，利用已经转换为伪寄存器引用的负载，使得存储器移动的障碍较少。 因此，编译器从SSA表示形成更高效的注册升级可执行程序代码。

公开(公告)号：US06301704B1

公开(公告)日：2001-10-09

申请号：US09097672

申请日：1998-06-16

申请人： Frederick Chow ,  Sun Chan ,  Peter Dahl ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich ,  Peng Tu

发明人： Frederick Chow ,  Sun Chan ,  Peter Dahl ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich ,  Peng Tu

IPC分类号： G06F9445

CPC分类号： G06F8/443

摘要： A method, system, and computer product uses a hashed static single assignment (SSA) form as a program representation and a medium for performing global scalar optimization. A compiler, after expressing the computer program in SSA form, can perform one or more static single assignment (SSA)-based, SSA-preserving global scalar optimization procedures on the SSA representation. Such a procedure modifies, (i.e., optimizes) the SSA representation of the program while preserving the utility of its embedded use-deprogram information for purposes of subsequent SSA-based, SSA-preserving global scalar optimizations. This saves the overhead expense of having to explicitly regenerate use-def program information for successive SSA-based, SSA-preserving global scalar optimizations.

摘要翻译： 方法，系统和计算机产品使用散列静态单赋值（SSA）形式作为程序表示和用于执行全局标量优化的介质。 在以SSA形式表达计算机程序之后，编译器可以在SSA表示上执行一个或多个基于静态单一分配（SSA）的SSA保留的全局标量优化过程。 这样的过程修改（即优化）程序的SSA表示，同时保留其嵌入的使用 - 解除程序信息的用途，以用于随后的基于SSA的SSA保留的全局标量优化。 这节省了为连续的基于SSA，保持SSA的全局标量优化显式地重新生成use-def程序信息的开销费用。

公开(公告)号：US6151706A

公开(公告)日：2000-11-21

申请号：US97715

申请日：1998-06-16

申请人： Raymond Lo ,  Frederick Chow

发明人： Raymond Lo ,  Frederick Chow

IPC分类号： G06F9/45

CPC分类号： G06F8/445

摘要： A method, system, and computer program product for performing speculative code motion within a sparse partial redundancy elimination (PRE) framework. Speculative code motion (i.e., speculation) refers to the placement of computations by a compiler in positions in the program that results in some paths being executed more efficiently and some being executed less efficiently. A net speed-up is thus achieved when the improved paths are those executed more frequently during the program's execution. Two embodiments for performing speculative code motion within the PRE framework are presented: (1) a conservative speculation method used in the absence of profile data; and (2) a profile-driven speculation method used when profile data are available. In a preferred embodiment, the two methods may be performed within static single assignment PRE (SSAPRE) resulting in better optimized code.

摘要翻译： 用于在稀疏部分冗余消除（PRE）框架内执行推测性代码运动的方法，系统和计算机程序产品。 推测性代码运动（即推测）是指编译器在程序中的位置放置计算，这导致一些路径被执行得更有效，而一些执行效率较低。 因此，在程序执行期间更经常地执行改进的路径时，可以实现净加速。 提出了在PRE框架内执行推测性代码运动的两个实施例：（1）在不存在简档数据的情况下使用的保守推测方法; 和（2）当配置文件数据可用时使用的轮廓驱动的推测方法。 在优选实施例中，两种方法可以在静态单个分配PRE（SSAPRE）内执行，从而导致更好的优化代码。

公开(公告)号：US5734908A

公开(公告)日：1998-03-31

申请号：US455238

申请日：1995-05-31

申请人： Sun C. Chan ,  Frederick Chow ,  Shin-Ming Liu ,  Raymond W. Lo

发明人： Sun C. Chan ,  Frederick Chow ,  Shin-Ming Liu ,  Raymond W. Lo

IPC分类号： G06F9/45

CPC分类号： G06F8/445

摘要： A system and method for optimizing a source code representation comprising a plurality of basic blocks are described. The optimized source code representation is to be executed in a target machine. The system operates by selecting from the source code representation a basic block pair comprising a source basic block and one or more target basic blocks. An instruction in the source basic block is identified that can be moved from the source basic block to the target basic block(s) while preserving program semantics. Either the instruction or a representation of the instruction is moved from the source basic block to the target basic block(s) as a function of resource utilization of the target machine that would result from this movement.

摘要翻译： 描述用于优化包括多个基本块的源代码表示的系统和方法。 优化的源代码表示将在目标机器中执行。 该系统通过从源代码表示中选择包括源基本块和一个或多个目标基本块的基本块对来进行操作。 识别源基本块中的指令，其可以从源基本块移动到目标基本块，同时保留程序语义。 根据该移动导致的目标机器的资源利用率，将指令或指令的表示从源基本块移动到目标基本块。

公开(公告)号：US5386562A

公开(公告)日：1995-01-31

申请号：US882427

申请日：1992-05-13

申请人： Suneel Jain ,  Frederick Chow ,  Sun Chan ,  Sin S. Lew

发明人： Suneel Jain ,  Frederick Chow ,  Sun Chan ,  Sin S. Lew

IPC分类号： G06F9/45 ,  G06F9/30 ,  G06F9/00

CPC分类号： G06F8/452

摘要： A procedure which is a particular type of software pipelining is provided which increases the efficiency with which code is executed by reducing or eliminating stalls such as by filling delay slots. The process includes moving instructions in a loop from one loop iteration to another. The moving of instructions provides the scheduler with additional independent instructions in a given basic block so the scheduler has greater freedom to move instructions into unfilled delay slots. The procedure includes changing the entry point into the loop, thus effectively moving an instruction from near the top of the loop to near the bottom of the loop, while changing the iteration number of the moved instruction.

摘要翻译： 提供了作为特定类型的软件流水线化的过程，其通过减少或消除诸如通过填充延迟时隙的失速来提高代码执行的效率。 该过程包括将循环中的指令从一个循环迭代移动到另一个循环迭代。 指令的移动向调度器提供给定基本块中的附加独立指令，因此调度器具有将指令移动到未填充延迟时隙的更大自由度。 该过程包括将入口点更改为循环，从而有效地将指令从循环顶部附近移动到靠近循环底部，同时改变移动指令的迭代次数。

公开(公告)号：US20050138244A1

公开(公告)日：2005-06-23

申请号：US10745259

申请日：2003-12-23

申请人： Jia-Ji Liu ,  Frederick Chow

发明人： Jia-Ji Liu ,  Frederick Chow

IPC分类号： G06F3/00 ,  G06F9/48

CPC分类号： G06F9/4887

摘要： A method and program are disclosed for scheduling operations in a digital processing system. The method includes monitoring one or more operations to be scheduled, sorting the operations based on their respective deadline processing cycles for scheduling, and storing the sorted operations in a queue. The operations are scheduled by adjusting their schedule time based on the updated system resource usage.

摘要翻译： 公开了用于数字处理系统中的调度操作的方法和程序。 该方法包括监视要调度的一个或多个操作，基于它们各自的调度的最终期限处理周期对操作进行排序，以及将排序的操作存储在队列中。 通过根据更新的系统资源使用情况调整其调度时间来调度操作。