专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明申请

US20050138244A1 Lower bound algorithm for operation scheduling 审中-公开
标题翻译：下限运算调度算法
公开(公告)号：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.
摘要翻译：公开了用于数字处理系统中的调度操作的方法和程序。该方法包括监视要调度的一个或多个操作，基于它们各自的调度的最终期限处理周期对操作进行排序，以及将排序的操作存储在队列中。通过根据更新的系统资源使用情况调整其调度时间来调度操作。

2. 发明授权

US06301704B1 Method, system, and computer program product for using static single assignment form as a program representation and a medium for performing global scalar optimization 失效
标题翻译：使用静态单一分配形式作为程序表示的方法，系统和计算机程序产品以及用于执行全局标量优化的介质
公开(公告)号：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程序信息的开销费用。

3. 发明授权

US6151706A Method, system, and computer program product for extending sparse partial redundancy elimination to support speculative code motion within an optimizing compiler 失效
标题翻译：方法，系统和计算机程序产品，用于扩展稀疏部分冗余消除，以支持优化编译器内的推测性代码运动
公开(公告)号：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）内执行，从而导致更好的优化代码。

4. 发明授权

US6026241A System, method, and computer program product for partial redundancy elimination based on static single assignment form during compilation 失效
标题翻译：编译过程中基于静态单个分配表的部分冗余消除的系统，方法和计算机程序产品
公开(公告)号：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。

5. 发明授权

US5768596A System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation 失效
公开(公告)号：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.

6. 发明授权

US5734908A System and method for optimizing a source code representation as a function of resource utilization 失效
标题翻译：用于优化作为资源利用的函数的源代码表示的系统和方法
公开(公告)号：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.
摘要翻译：描述用于优化包括多个基本块的源代码表示的系统和方法。优化的源代码表示将在目标机器中执行。该系统通过从源代码表示中选择包括源基本块和一个或多个目标基本块的基本块对来进行操作。识别源基本块中的指令，其可以从源基本块移动到目标基本块，同时保留程序语义。根据该移动导致的目标机器的资源利用率，将指令或指令的表示从源基本块移动到目标基本块。

7. 发明授权

US5386562A Circular scheduling method and apparatus for executing computer programs by moving independent instructions out of a loop 失效
标题翻译：通过将独立指令移出循环来执行计算机程序的循环调度方法和装置
公开(公告)号：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.
摘要翻译：提供了作为特定类型的软件流水线化的过程，其通过减少或消除诸如通过填充延迟时隙的失速来提高代码执行的效率。该过程包括将循环中的指令从一个循环迭代移动到另一个循环迭代。指令的移动向调度器提供给定基本块中的附加独立指令，因此调度器具有将指令移动到未填充延迟时隙的更大自由度。该过程包括将入口点更改为循环，从而有效地将指令从循环顶部附近移动到靠近循环底部，同时改变移动指令的迭代次数。

8. 发明授权

US06571387B1 Method and computer program product for global minimization of sign-extension and zero-extension operations 有权
标题翻译：用于全局最小化符号扩展和零延伸操作的方法和计算机程序产品
公开(公告)号：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基准，从而加速执行编译程序。

9. 发明授权

US6131189A System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation 失效
标题翻译：在编译期间，以静态单个分配形式有效地表示别名和间接记忆操作的系统和方法
公开(公告)号：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函数。优化器散列唯一的值编号，并为每个变量版本创建相应的哈希表条目，并在重命名所有零版本后剩余的每个虚拟变量。优化器还对程序的每个基本块应用全局值编号。

10. 发明授权

US06128775A Method, system, and computer program product for performing register promotion via load and store placement optimization within an optimizing compiler 失效
标题翻译：方法，系统和计算机程序产品，用于通过优化编译器中的加载和存储放置优化来执行注册促进
公开(公告)号：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表示形成更高效的注册升级可执行程序代码。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式