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

1. 发明授权

US5774730A Method and apparatus for improving colorability of constrained nodes in an interference graph within a computer system 失效
标题翻译：用于改善计算机系统内的干涉图中约束节点的着色性的方法和装置
公开(公告)号：US5774730A
公开(公告)日：1998-06-30
申请号：US509637
申请日：1995-07-31
申请人： Nava Arela Aizikowitz , Liviu Asnash , Roy Bar-Haim , Orit Edelstein , Mircea Namolaru , Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
发明人： Nava Arela Aizikowitz , Liviu Asnash , Roy Bar-Haim , Orit Edelstein , Mircea Namolaru , Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
IPC分类号： G06F9/45
CPC分类号： G06F8/433 , G06F8/441
摘要： A method and apparatus for coloring an interference graph yields a higher number of colored nodes by taking into consideration the colors of neighbors of a node's uncolored constrained neighbors. By assigning a color to a node that is also the color of a neighbor of an uncolored constrained neighbor, one color constraint is removed, increasing the probability of coloring the uncolored constrained neighbor. If more than one of the neighbors of the uncolored constrained neighbors are colored, one of the colors may be selected over the others using an appropriate heuristic.
摘要翻译：通过考虑节点的未着色约束邻居的邻居的颜色，用于着色干涉图的方法和装置产生更多数量的彩色节点。通过将颜色分配给也是未着色约束邻居的邻居的颜色的节点，消除了一个颜色约束，增加了对着色约束邻居着色的可能性。如果超过一个未着色约束邻居的邻居被着色，则可以使用适当的启发式来选择其中一种颜色。

2. 发明授权

US5946491A Register allocation method and apparatus for gernerating spill code as a function of register pressure compared to dual thresholds 失效
标题翻译：用于产生溢出码的寄存器分配方法和装置作为与双阈值相比的寄存器压力的函数
公开(公告)号：US5946491A
公开(公告)日：1999-08-31
申请号：US660703
申请日：1996-06-06
申请人： Nava Arela Aizikowitz , Liviu Asnash , Roy Bar-Haim , Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
发明人： Nava Arela Aizikowitz , Liviu Asnash , Roy Bar-Haim , Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
IPC分类号： G06F9/45
CPC分类号： G06F8/441
摘要： A method and apparatus for minimizing spill code in regions of low register pressure determines the register pressure at various locations in the computer program. When a live range is selected for spilling, spill code is generated to relieve the register pressure in regions of high register pressure, while spill code is avoided in regions of low register pressure. In this manner a minimum amount of spill code is generated, enhancing both the compile time and the run time of the resultant instruction stream.
摘要翻译：用于使寄存器压力低的区域中的溢出码最小化的方法和装置决定了计算机程序中各个位置的寄存器压力。当选择生存区域进行溢出时，产生溢出代码，以缓解高注册压力区域的注册压力，同时在低注册压力的区域避免泄漏代码。以这种方式，产生最小量的溢出码，从而增强结果指令流的编译时间和运行时间。

3. 发明授权

US5761514A Register allocation method and apparatus for truncating runaway lifetimes of program variables in a computer system 失效
标题翻译：用于截断计算机系统中程序变量失控寿命的寄存器分配方法和装置
公开(公告)号：US5761514A
公开(公告)日：1998-06-02
申请号：US522052
申请日：1995-08-31
申请人： Nava Arela Aizikowitz , Roy Bar-Haim , Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
发明人： Nava Arela Aizikowitz , Roy Bar-Haim , Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
IPC分类号： G06F9/45
CPC分类号： G06F8/433 , G06F8/441
摘要： A method and apparatus for truncating runaway lifetimes of program variables calculates liveness for each variable based on upwardly exposed uses. Reaching definitions are then calculated for at least the program variables that have runaway lifetimes. The liveness information is compared to the reaching definition information to determine whether a variable that is live upon entry to a basic block has a definition that reaches the end of each predecessor block, or has a use within the basic block. If the reaching definition for a variable reaches the beginning of the block and if there is a predecessor block for which there is no reaching definition, the variable has a runaway lifetime. The variable also has a runaway lifetime if there is a use of the variable in a block without a reaching definition for the variable at the beginning of the block. The runaway lifetime is truncated by inserting an instruction such as a pseudo-definition of the variable into the instruction stream at an appropriate place. Once runaway lifetimes are truncated using this method, subsequent stages of the compiler may calculate liveness by performing a single dataflow analysis which calculates lifetimes based on upwardly exposed uses.
摘要翻译：用于截断程序变量的失效寿命的方法和装置根据向上暴露的使用来计算每个变量的活动性。然后对至少具有失效寿命的程序变量计算达到定义。将活动信息与达到的定义信息进行比较，以确定在输入到基本块时是否存在活动的变量具有到达每个前导块的结束的定义，或者在基本块内具有使用。如果变量的到达定义到达块的开头，并且如果存在没有到达定义的前导块，则该变量具有失控的生命周期。如果块中的变量使用块的开头处的变量没有达到定义，那么该变量也将失效。通过在适当的地方将诸如伪变量的伪定义的指令插入指令流来截断失控生命周期。一旦使用这种方法截断失效生命周期，编译器的后续阶段可以通过执行基于向上暴露的使用计算寿命的单个数据流分析来计算活动。

4. 发明授权

US06301652B1 Instruction cache alignment mechanism for branch targets based on predicted execution frequencies 失效
标题翻译：基于预测执行频率的分支目标的指令缓存对齐机制
公开(公告)号：US06301652B1
公开(公告)日：2001-10-09
申请号：US08593309
申请日：1996-01-31
申请人： Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
发明人： Edward Curtis Prosser , Robert Ralph Roediger , William Jon Schmidt
IPC分类号： G06F940
CPC分类号： G06F8/4442
摘要： A compiler system and method is provided that can 1) generate a second instruction stream from a first instruction stream, 2) read in and process predetermined external information regarding the basic blocks that makes up the second instruction stream and 3) place certain of the basic blocks on cache line boundaries based on predicted execution frequencies. In particular, the compiler system and method utilize profile information containing predicted block execution or edge-weight execution frequencies to determine which of the basic blocks to align on cache line boundaries. One method for obtaining profile information includes precompiling the source code, creating an executable program, executing the program with test inputs, and outputting a profile containing execution frequency information. Once the profile information is obtained, the source code can then be recompiled using the profile information. The compiler can then selectively cache align those blocks identified as important.
摘要翻译：提供一种编译器系统和方法，其可以1）从第一指令流生成第二指令流，2）读入并处理关于组成第二指令流的基本块的预定外部信息，以及3）将某些基本基于预测的执行频率在高速缓存线边界上的块。特别地，编译器系统和方法利用包含预测块执行或边缘权重执行频率的简档信息来确定哪些基本块在高速缓存行边界上对齐。用于获得简档信息的一种方法包括预编译源代码，创建可执行程序，使用测试输入执行程序，以及输出包含执行频率信息的简档。一旦获得了简档信息，就可以使用简档信息重新编译源代码。然后，编译器可以选择性地高速缓存将被标识为重要的块。

5. 发明授权

US5937196A Compiling with partial copy propagation 失效
标题翻译：使用部分复制传播进行编译
公开(公告)号：US5937196A
公开(公告)日：1999-08-10
申请号：US933705
申请日：1997-09-19
申请人： William Jon Schmidt , Edward Curtis Prosser , Robert Ralph Roediger
发明人： William Jon Schmidt , Edward Curtis Prosser , Robert Ralph Roediger
IPC分类号： G06F9/45
CPC分类号： G06F8/443
摘要： A compiler and method of compiling provide partial redundant copy elimination by eliminating copy statements having at least one eligible reachable use and at least one ineligible reachable use. To eliminate such statements, the used operand of each eligible use is replaced with the used operand in the copy statement, and the copy statement is duplicated prior to each ineligible use.
摘要翻译：编译器和编译方法通过消除具有至少一个符合条件的可达使用和至少一个不合格可达的使用的复制语句来提供部分冗余复制消除。为了消除这种陈述，每个合格使用的使用操作数被替换为复制语句中使用的操作数，并且在每个不合格使用之前复制副本。

6. 发明授权

US07120907B2 Unrolling loops with partial hot traces 失效
标题翻译：展开循环与部分热痕迹
公开(公告)号：US07120907B2
公开(公告)日：2006-10-10
申请号：US10650544
申请日：2003-08-28
申请人： Robert Ralph Roediger , William Jon Schmidt , Peter Jerome Steinmetz
发明人： Robert Ralph Roediger , William Jon Schmidt , Peter Jerome Steinmetz
IPC分类号： G06F9/45 , G06F15/00
CPC分类号： G06F8/443
摘要： Methods and apparatus are disclosed for improved loop unrolling by a compiler. A large class of loops exists for which effective loop unrolling has not previously been performed because they are too large to be completely unrolled, but which do not have a single hot trace that covers an entire loop iteration. The present invention recognizes such loops that have partial hot traces identified using profile data. A set of instructions which constitute a proper superset of the hot trace and a proper subset of the entire loop, and which forms a complete loop iteration is identified. This set of instructions can then be unrolled without unrolling the entire loop.
摘要翻译：公开了用于由编译器改进循环展开的方法和装置。存在一个大类的循环，由于它们太大而不能完全展开，因此没有执行有效循环展开，因为它们没有覆盖整个循环迭代的单个热跟踪。本发明识别使用简档数据识别的部分热迹的这种循环。识别构成热跟踪的正确超集和整个循环的适当子集并且形成完整循环迭代的一组指令。然后可以展开这组指令，而不会展开整个循环。

7. 发明授权

US06938249B2 Compiler apparatus and method for optimizing loops in a computer program 有权
标题翻译：用于优化计算机程序中的循环的编译器装置和方法
公开(公告)号：US06938249B2
公开(公告)日：2005-08-30
申请号：US09992324
申请日：2001-11-19
申请人： Robert Ralph Roediger , William Jon Schmidt
发明人： Robert Ralph Roediger , William Jon Schmidt
IPC分类号： G06F9/45 , G06F11/34
CPC分类号： G06F11/3466 , G06F8/443 , G06F2201/865
摘要： A profile-based loop optimizer generates an execution frequency table for each loop that gives more detailed profile data that allows making a more intelligent decision regarding if and how to optimize each loop in the computer program. The execution frequency table contains entries that correlate a number of times a loop is executed each time the loop is entered with a count of the occurrences of each number during the execution of an instrumented instruction stream. The execution frequency table is used to determine whether there is one dominant mode that appears in the profile data, and if so, optimizes the loop according to the dominant mode. The optimizer may perform optimizations by peeling a loop, by unrolling a loop, and by performing both peeling and unrolling on a loop according to the profile data in the execution frequency table for the loop. In this manner the execution time of the resulting code is minimized according to the detailed profile data in the execution frequency tables, resulting in a computer program with loops that are more fully optimized.
摘要翻译：基于配置文件的循环优化器为每个循环生成执行频率表，以提供更详细的配置文件数据，从而可以对计算机程序中的每个循环是否以及如何优化。执行频率表包含将在每次循环输入时执行循环的次数与执行被测试指令流期间每个数字的出现次数相关联的条目。执行频率表用于确定在配置文件数据中是否存在一个主要模式，如果是，则根据主导模式优化循环。优化器可以通过剥离循环，展开循环，以及根据循环的执行频率表中的轮廓数据在循环上执行剥离和展开来执行优化。以这种方式，根据执行频率表中的详细简档数据，最终得到的代码的执行时间最小化，从而导致具有更完全优化的循环的计算机程序。

8. 发明授权

US6029004A Method and apparatus for modular reordering of portions of a computer program based on profile data 失效
标题翻译：基于简档数据对计算机程序的部分进行模块化重排序的方法和装置
公开(公告)号：US6029004A
公开(公告)日：2000-02-22
申请号：US819526
申请日：1997-03-17
申请人： Vita Bortnikov , Bilha Mendelson , Mark Novick , Robert Ralph Roediger , William Jon Schmidt , Inbal Shavit-Lottem
发明人： Vita Bortnikov , Bilha Mendelson , Mark Novick , Robert Ralph Roediger , William Jon Schmidt , Inbal Shavit-Lottem
IPC分类号： G06F9/45 , G06F9/44
CPC分类号： G06F8/445
摘要： An apparatus and method reorder portions of a computer program in a way that achieves both enhanced performance and maintainability of the computer program. A global call graph is initially constructed that includes profile data. From the information in the global call graph, an intramodular call graph is generated for each module. Reordering techniques are used to reorder the procedures in each module according to the profile data in each intramodular call graph. An intermodular call graph is generated from the information in the global call graph. Reordering techniques are used to reorder the modules in the computer program. By reordering procedures within modules, then reordering the modules, enhanced performance is achieved without reordering procedures across module boundaries. Respecting module boundaries enhances the maintainability of the computer program by allowing a module to be replaced without adversely affecting the other modules while still providing many of the advantages of global procedure reordering.
摘要翻译：一种装置和方法以实现计算机程序的增强的性能和可维护性的方式重新排序计算机程序的部分。最初构建包括配置文件数据的全局调用图。从全局调用图中的信息，为每个模块生成一个集体内调用图。根据每个模块间调用图中的配置文件数据，重新排序技术用于对每个模块中的过程重新排序。从全局调用图中的信息生成一个多模式调用图。重新排序技术用于重新排序计算机程序中的模块。通过重新排序模块中的过程，然后重新排序模块，实现增强的性能，而无需跨模块边界重新排序过程。尊重模块边界通过允许更换模块而不会对其他模块产生不利影响，从而提高计算机程序的可维护性，同时仍然提供全局过程重新排序的许多优点。

9. 发明授权

US06308324B1 Multi-stage profiler 失效
标题翻译：多级分析仪
公开(公告)号：US06308324B1
公开(公告)日：2001-10-23
申请号：US09329404
申请日：1999-06-10
申请人： Robert Ralph Roediger , William Jon Schmidt
发明人： Robert Ralph Roediger , William Jon Schmidt
IPC分类号： G06F945
CPC分类号： G06F11/3466 , G06F8/4451 , G06F2201/865 , G06F2201/88
摘要： A profiler that operates in a multi-stage environment is disclosed. As program code undergoes a series of transformations, branches of interest are selected and tracked. Regardless of how many transformations are involved only a single instrumentation/data gathering phase is required. The gathered profile data is then used to perform various optimizations at the differing transformation stages.
摘要翻译：公开了在多级环境中操作的分析器。随着程序代码经历一系列转换，选择和跟踪感兴趣的分支。无论涉及多少变革，只需要一个仪器/数据采集阶段。收集的轮廓数据然后用于在不同的转换阶段执行各种优化。

10. 发明授权

US06983459B1 Incorporating register pressure into an inlining compiler 失效
标题翻译：将寄存器压力并入到内联编译器中
公开(公告)号：US06983459B1
公开(公告)日：2006-01-03
申请号：US09286862
申请日：1999-04-06
申请人： Edward Curtis Prosser , William Jon Schmidt
发明人： Edward Curtis Prosser , William Jon Schmidt
IPC分类号： G06F9/45
CPC分类号： G06F8/4443
摘要： A method, system, and program product for optimizing compilation. In the preferred embodiment, a compiler compiles a source-code file twice; once to gather register-pressure data, and a second time to apply the data. Thus, the compiler saves register-pressure data during the first compilation and uses it during the second compilation to make informed inlining decisions. The compiler saves two kinds of data during the first compilation: (1) the maximum register-pressure occurring in each procedure; and (2) within each procedure, the register pressure at each call site that is a potential inlining candidate. This data is then fed into the compiler during the second compilation. The compiler uses the data during the second compilation in two ways. First, when deciding whether to inline a child procedure into a parent procedure, the compiler determines whether the sum of the maximum register-pressure and the site register-pressure exceeds the number of available, physical registers. If so, the inlining is not done. Otherwise, inlining is permitted subject to other heuristics. Second, if the child procedure is chosen for inlining into the parent procedure, the maximum register-pressure of the parent procedure is set to be the maximum of its existing value or the sum of the maximum register-pressure of the child procedure and the site register-pressure. This assures that later consideration of the parent procedure for inlining into another procedure can be done with accurate register-pressure data available.
摘要翻译：一种用于优化编译的方法，系统和程序产品。在优选实施例中，编译器编译源代码文件两次; 一次收集注册压力数据，并第二次应用数据。因此，编译器在第一次编译期间保存注册表压力数据，并在第二次编译期间使用它来作出明确的内联决策。编译器在第一次编译时保存两种数据：（1）每个过程中发生的最大寄存器压力; 和（2）在每个程序中，每个呼叫站点的注册压力是潜在的内联候选人。然后在第二次编译期间将该数据提供给编译器。编译器在第二次编译期间使用数据有两种方式。首先，当决定是否将子程序嵌入到父程序中时，编译器确定最大寄存器压力和站点寄存器压力的总和是否超过可用的物理寄存器的数量。如果是这样，内联没有完成。否则，允许内联使用其他启发式。第二，如果选择子程序来嵌入父级程序，父级程序的最大注册压力被设置为其现有值的最大值或子程序与站点的最大注册压力之和记录压力。这样做可以使用精确的寄存器压力数据来进行后续审核。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式