Method and apparatus for direct conversion of programs in object code form between different hardware architecture computer systems

Claim 1

A method for use in a computer system for processing a first version of a non-source-code computer program expressed in terms of a first instruction set, at least ones of the instructions of said first instruction set having primary and side effects, said method comprising the computer-implemented steps of: expanding each of at least ones of the instructions of said non-source-code first version into a plurality of instructions which explicitly replicate the primary and side effects of said each instruction of said first version, and processing the resulting expanded version to eliminate individual ones of the instructions thereof whose elimination does not affect the functionality of said program, said processing step including the step of performing data flow analysis over said expanded version to identify said individual instructions, and including the further step of identifying procedures within said expanded version, said data flow analysis step being performed globally over said expanded version on a procedure-by-procedure basis, each of said procedures being comprised of all basic blocks within said expanded version reachable from a respective procedure head block a) which are not themselves procedure head blocks and b) to which flow of control does not pass through any intermediate procedure head block, a basic block being a sequence of instructions of said expanded version that has exactly one instruction at which control can enter the sequence during execution and exactly one instruction at which control leaves the sequence during execution, and a procedure head block being a basic block whose entry point is either an entry point of said expanded version or is the target of a call instruction thereof, at least ones of said procedures including definitions of values of variables, which values have uses in at least one other procedure, and said data flow analysis step including the step of associating such definitions with such uses, said processing step further including the step of creating a call tree identifying the calling relationships among said procedures, and said associating step including the sequential steps of processing said procedures in forward call tree order to create a list of those variables used in a procedure that a) are at least potentially defined by a procedure called thereby and b) are used, after the call, in the calling procedure, and processing said procedures in reverse call tree order to exclude from said list those variables which are not actually defined by the call procedure.

Claim 2

A method for use in a computer system for processing a first version of a non-source-code computer program expressed in terms of a first instruction set, at least ones of the instructions of said first instruction set having primary and side effects, said method comprising the computer-implemented steps of: expanding each of at least ones of the instructions of said non-source-code first version into a plurality of instructions which explicitly replicate the primary and side effects of said each instruction of said first version, and processing the resulting expanded version to eliminate individual ones of the instructions thereof whose elimination does not affect the functionality of said program, said processing step including the step of performing data flow analysis over said expanded version to identify said individual instructions, and including the further step of identifying procedures within said expanded version, said data flow analysis step being performed globally over said expanded version on a procedure-by-procedure basis, each of said procedures being comprised of all basic blocks within said expanded version reachable from a respective procedure head block a) which are not themselves procedure head blocks and b) to which flow of control does not pass through any intermediate procedure head block, a basic block being a sequence of instructions of said expanded version that has exactly one instruction at which control can enter the sequence during execution and exactly one instruction at which control leaves the sequence during execution, and a procedure head block being a basic block whose entry point is either an entry point of said expanded version or is the target of a call instruction thereof, at least ones of said procedures including definitions of values of variables, which values have uses in at least one other procedure, and said data flow analysis step including the step of associating such definitions with such uses, said processing step further including the step of creating a call tree identifying the calling relationships among said procedures, and said associating step including the sequential steps of processing said procedures in forward call tree order to create a list of those variables used in a procedure that a) are at least potentially defined by a procedure called thereby and b) are used, after the call, in the calling procedure, and processing said procedures in reverse call tree order to exclude from said list those variables which are not actually defined by the call procedure.

Claim 3

An apparatus for processing a first version of a non-source-code computer program expressed in terms of a first instruction step, at least ones of the instructions of said first instruction set having primary and side effects, comprising: means for expanding each of at least ones of the instructions of said non-source-code first version into a plurality of instructions which explicitly replicate the primary and side effects of said each instructions of said first version, and means for processing the resulting expanded version to eliminate individual ones of the instructions thereof whose elimination does not affect the functionality of said program, said means for processing comprising a means for performing data flow analysis over said expanded version to identify said individual instructions and comprising further a means for identifying procedures within said expanded version, said data flow analysis being performed globally over said expanded version on a procedure-by-procedure basis, each of said procedures being comprised of all basic blocks within said expanded version reachable from a respective procedure head block a) which are not themselves procedure head blocks and b) to which flow of control does not pass through any intermediate procedure head block, a basic block being a sequence of instructions of said expanded version that has exactly one instruction at which control can enter the sequence during execution and exactly one instruction at which control leaves the sequence during execution, and a procedure head block being a basic block whose entry point is either an entry point of said expanded version or is the target of a call instruction thereof, at least ones of said procedures including definitions of values of variables, which values have uses in at least one other procedure, and said data flow analysis means comprising a means of associating such definitions with such uses, said processing means further comprising a means for creating a call tree identifying the calling relationships among said procedures, said associating means comprising: a means for processing said procedures in forward call tree order to create a list of those variables used in the procedure that (a) are at least potentially defined by a procedure called thereby and (b) are used, after the call, in the calling procedure, and a means for processing said procedures in reverse call tree order to exclude from said list those variables which are not actually defined by the call procedure.

Claim 4

An apparatus for processing a first version of a non-source-code computer program expressed in terms of a first instruction step, at least ones of the instructions of said first instruction set having primary and side effects, comprising: means for expanding each of at least ones of the instructions of said non-source-code first version into a plurality of instructions which explicitly replicate the primary and side effects of said each instructions of said first version, and means for processing the resulting expanded version to eliminate individual ones of the instructions thereof whose elimination does not affect the functionality of said program, said means for processing comprising a means for performing data flow analysis over said expanded version to identify said individual instructions and comprising further a means for identifying procedures within said expanded version, said data flow analysis being performed globally over said expanded version on a procedure-by-procedure basis, each of said procedures being comprised of all basic blocks within said expanded version reachable from a respective procedure head block a) which are not themselves procedure head blocks and b) to which flow of control does not pass through any intermediate procedure head block, a basic block being a sequence of instructions of said expanded version that has exactly one instruction at which control can enter the sequence during execution and exactly one instruction at which control leaves the sequence during execution, and a procedure head block being a basic block whose entry point is either an entry point of said expanded version or is the target of a call instruction thereof, at least ones of said procedures including definitions of values of variables, which values have uses in at least one other procedure, and said data flow analysis means comprising a means of associating such definitions with such uses, said processing means further comprising a means for creating a call tree identifying the calling relationships among said procedures, said associating means comprising: a means for processing said procedures in forward call tree order to create a list of those variables used in the procedure that (a) are at least potentially defined by a procedure called thereby and (b) are used, after the call, in the calling procedure, and a means for processing said procedures in reverse call tree order to exclude from said list those variables which are not actually defined by the call procedure.