Hewlett-Packard Development Company, L.p.

Hewlett-Packard Company

Vasanth Bala

Evelyn Duesterwald

Sanjeev Banerjia

Paolo Faraboschi

Giuseppe Desoli

Dz-Ching Ju

Carol Linda Thompson

Vatsa Santhanam

The present invention provides for native execution of an application on a client using code segments transmitted from a server over a network. The server includes an application code source, and a server code segment manager. The server may also include an application code transformation manager if the code source is not in the native binary format of the client. The client includes a client code segment manager, a code cache linker and manager, a code cache, and a CPU. When the client seeks to execute an application, code segments are transmitted from the server to the client and are stored in the code cache. The CPU then executes the code segments natively. When a code segment branches to a segment not in the cache, control passes to the client code segment manager, which requests the needed code segment from the server code segment manager of the server.

Networked client-server architecture for transparently transforming and executing applications

A &#x3a6; function provides a mechanism for static single assignment in the presence of predicated code. Guards placed on each source operand of the &#x3a6; function indicate the condition under which the corresponding source operand is live and provide correct materialization of the &#x3a6; functions after code reordering. For control functions &#x3a6;representing a confluence of live reaching definitions at a join point in the control flow graph, the guards indicate the basic block which is the source of the edge associated with the source operand. The &#x3a6;operands are paired with the source basic block of the incoming edge(s) along which they are live. The operands are also ordered according to a topological ordering of their associated block. This ordering is maintained through subsequent code transformations. In the topological ordering, the source of the edge from which the definition was passed is defined. A predicate &#x3a6; function &#x3a6;, represents the confluence of definitions in a straight line of code in which some of the definitions have been predicated. For &#x3a6;, the guards on the source operands indicate the predicate under which the corresponding operand is live. The order of the operands is such that the &#x3a6;function can be fully materialized by inserting a copy from each source operand to the target variable, in the corresponding order, and each predicated by the associated predicate guard.

Method and apparatus for ordered predicate phi in static single assignment form

An optimization scheme used at run-time or compile-time is capable of identifying partially redundant loads and determining whether the load is truly redundant. The truly redundant load may be replaced with a register copy instruction to reduce the memory traffic and save CPU cycle time.

Memory disambiguation scheme for partially redundant load removal

A method for growing a secondary trace out of a cache of translations for a program during the program's execution in a dynamic translator, comprising the steps of: maintaining execution counts for translation heads that are executed from a code cache; when an execution count for one of said translation heads exceeds a threshold, designated as a hot translation head, beginning a mode of operation in which, as following code translations are executed from the code cache after the execution of the hot translation head, storing in a history buffer information identifying each of the following code translations in sequence; terminating the storing of information in the history buffer in relation to the hot translation head when a termination condition is met; and linking together the translation head and the sequence of following code translations identified in the history buffer to form a larger code translation.

Secondary trace build from a cache of translations in a caching dynamic translator

In a system and method for linking and unlinking code fragments stored in a code cache, a memory area is associated with a branch in a first code fragment that branches outside the cache. If the branch can be set to branch to a location in a second code fragment stored in the cache, branch reconstruction information is stored in the memory area associated with the branch, and the branch instruction is updated to branch to the location in the second code fragment, thereby linking the first code fragment to the second code fragment. If it is determined that the previously linked branch should be unlinked, the first and second code fragments at that branch are unlinked by reading the information stored in the associated memory area at the time of linking, and using that information to reset the branch to its state prior to the linking.

Method and system for fast unlinking of a linked branch in a caching dynamic translator

A method and apparatus for selecting hot traces for translation and/or optimization is described in the context of a caching dynamic translator. The code cache stores hot traces. Profiling is done at locations that satisfy a start-of-trace condition, e.g., the targets of backward taken branches. A hot target of a backward taken branch is speculatively identified as the beginning of a hot trace, without the need to profile the blocks that make up the trace. The extent of the speculatively selected hot trace is determined by an end-of-trace condition, such as a backward taken branch or a number of interpreted or native instructions. The interpreter is augmented with a mode in which it emits native instructions that are cached. A trace is cached by identifying a hot start of a trace and then continuing interpretation while storing the emitted native instruction stream until an end-of-trace condition is met.

Low overhead speculative selection of hot traces in a caching dynamic translator

A method is shown for selecting active, or hot, code traces in an executing program for storage in a code cache. A trace is a sequence of dynamic instructions characterized by a start address and a branch history which allows the trace to be dynamically disassembled. Each trace is terminated by execution of a trace terminating condition which is a backward taken branch, an indirect branch, or a branch whose execution causes the branch history for the trace to reach a predetermined limit. As each trace is generated by the executing program, it is loaded into a buffer for processing. When the buffer is full, a counter corresponding to the start address of each trace is incremented. When the count for a start address exceeds a threshold, then the start address is marked as being hot. Each hot trace is then checked to see if the next trace in the buffer shares the same start address, in which case the hot trace is cyclic. If the start address of the next trace is not the same as the hot trace, then the traces in the buffer are checked to see they form a larger cycle of execution. If the traces subsequent to the hot trace are not hot themselves and are followed by a trace having the same start address as the hot trace, then their branch histories are companded with the branch history of the hot trace to form a cyclic trace. The cyclic traces are then disassembled and the instructions executed in the trace are stored in a code cache.

Method for selecting active code traces for translation in a caching dynamic translator

Cache apparatus and method with a cache replacement strategy that preemptively evicts native code translations from a code cache, independent of a space shortage in the code cache. Replacement timing is based on detection by the dynamic translator of a change in a parameter that is indicative of either two things: 1) a change in the working set of the program being translated (a parameter such as a translation rate) or 2) a change in the paths being exercised within the current working set of the program being translated (a parameter such as or the accuracy of branch predictions). This apparatus and method is described in the context of a dynamic translator.

Preemptive replacement strategy for a caching dynamic translator

An apparatus and method are shown for collecting a branch history value of a program executing in a processor. A current start address register latches a program count value in response to a trace termination condition, such as an indirect branch instruction. A current branch history register is cleared in response to the trace termination condition and shifts in a branch outcome value of the processor in response to a conditional direct branch instruction. A last trace start address latches the content of the current trace start address and a last branch history register latches the content of the current branch history register when a trace termination condition occurs.

Growing community of inventors

Sudbury, MA, United States of America

Vasanth Bala