公开(公告)号：US06301704B1

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

申请号：US09097672

申请日：1998-06-16

Applicant: Frederick Chow ,  Sun Chan ,  Peter Dahl ,  Robert Kennedy ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich ,  Peng Tu

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

IPC: G06F9445

CPC classification number: G06F8/443

Abstract: 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.

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

公开(公告)号：US6131189A

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

申请号：US979939

申请日：1997-11-26

Applicant: Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

Inventor： Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

IPC: G06F9/45

CPC classification number: G06F8/443

Abstract: 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.

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

公开(公告)号：US06789253B1

公开(公告)日：2004-09-07

申请号：US09363067

申请日：1999-07-28

Applicant: Mark Streich ,  Salil Pradhan ,  Eric Caspole

Inventor： Mark Streich ,  Salil Pradhan ,  Eric Caspole

IPC: G06F945

CPC classification number: G06F9/52

Abstract: A method, system, and apparatus for improving performance of multi-threaded computer programs that re-establishes the lock structure that enables access to a portion of the computer memory and thereby reduces contention for computer memory. The present invention analyzes the references to computer memory and re-structures the memory access lock structure and thereby improves the use of regions of computer memory that are found to be mutually exclusive.

Abstract translation: 一种用于改进多线程计算机程序的性能的方法，系统和装置，其重新建立能够访问计算机存储器的一部分并因此减少计算机存储器争用的锁结构。 本发明分析了对计算机存储器的参考，并重新构建了存储器访问锁定结构，从而改进了被认为是相互排斥的计算机存储器的区域的使用。

公开(公告)号：US5768596A

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

申请号：US636605

申请日：1996-04-23

Applicant: Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

Inventor： Frederick Chow ,  Sun Chan ,  Shin-Ming Liu ,  Raymond Lo ,  Mark Streich

IPC: G06F9/45

CPC classification number: G06F8/443

Abstract: 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.