Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2001-11-26
2004-12-21
Kim, Kenneth S. (Department: 2111)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C712S226000, C712S234000, C717S159000
Reexamination Certificate
active
06834383
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer-executable software, and more particularly to optimizing binary-level instructions.
BACKGROUND OF THE INVENTION
Today's computer programming languages support conditional branch instructions such as “if-then-else,” “while loops,” and the like. For computer program optimization, compression, testing, or other purposes, it may be beneficial to reorder code instructions to move instructions that are more likely to be executed together in the run of the program, closer together. The reordering of instructions can sometimes be facilitated by conditional branch reversals. A conditional branch reversal is an optimization technique that reverses the order of code instructions following a conditional branch instruction to improve program execution and to make more effective use of instruction cache.
Several computer architectures support a process of converting conditional branches in a program in order to utilize predicated execution at the binary code level. The process implements conditional branches in the binary code with comparison instructions that set a predicate or binary truth-value. Instructions that are control dependent on the branch are converted to predicated instructions dependent on the value of the corresponding predicate. Generalized predication provides the ability to determine whether or not to allow (i.e., guard) the execution of virtually any instruction with a runtime condition. However, guarding predicates create a barrier to branch-reversal optimizations that has no equivalent in source-code optimizations.
Additionally, branch reversals are difficult at the binary level in computer architectures that support the use of control speculative loading of instructions. A speculative load allows an instruction to execute before the processor knows if it is necessary. Typically, a special hardware bit exists that allows control speculation to proceed without causing unnecessary page faults or other exceptions. However, if a speculative load causes an exception, or faults, the exception is not handled until it's known that the load was actually necessary. Instead, the hardware tags the invalid results with the special hardware bit. The special hardware bit is propagated to all of the uses of the load. The result is that predicates may no longer reflect the correct truth-values. Thus, control speculative loading of instructions creates yet another hurdle to implement branch reversals at the binary level.
SUMMARY OF THE INVENTION
This summary of the invention section is intended to introduce the reader to aspects of the invention and is not a complete description of the invention. Particular aspects of the invention are pointed out in other sections herein below and the invention is set forth in the appended claims, which alone demarcate its scope.
The present invention is directed to a method of reversing branches at the binary level on computer architectures that support predicated execution. Briefly stated, described is a method that identifies a predicate expression representing conditions in predicated assembly language instructions that determine a direction of a conditional branch instruction. The predicate expression is employed to enable a transformation to be made that causes the conditional branch instruction to trigger, or execute, when an opposite condition is true.
In accordance with one aspect of the present invention, a computer-implemented method is directed to producing a binary-level conditional branch reversal within a binary program on a computer architecture that supports a predicated execution. The method includes obtaining a predicate expression representing a condition that influences a direction of program flow of the binary-level conditional branch to be reversed, determining a binary-level transformation that causes the binary-level conditional branch to be triggered when an opposite condition is true, and modifying the binary-level conditional branch with the determined binary-level transformation, wherein the binary-level conditional branch is reversed.
In another aspect of the present invention, the above-described method further includes obtaining the predicate expression by uniquely identifying predicates that influence the direction of program flow of the binary-level conditional branch to be reversed, deducing relationships between the uniquely identified predicates, and based on the relationships between the uniquely identified predicates, determining at least one predicate that influences the direction of program flow of the binary-level conditional branch.
In yet another aspect of the present invention, a computer-implemented method is directed to obtaining a predicate expression that determines a guarding predicate of a binary-level conditional branch instruction within a binary program. The computer-implemented method includes uniquely identifying predicates that influence a direction of program flow of the binary-level conditional branch to be reversed, deducing relationships between the uniquely identified predicates, and based on the relationships between the uniquely identified predicates, determining at least one predicate that influences the direction of program flow of the binary-level conditional branch.
In still another aspect of the present invention, a computer-implemented method is directed to determining a binary-level transformation that causes a binary-level conditional branch within a binary program to be triggered when an opposite condition is true, comprising computing an inverse predicate expression that describes the opposite condition.
A more complete appreciation of the present invention and its improvements can be obtained by reference to the accompanying drawings, which are briefly summarized below, to the following detailed description of illustrative embodiments of the invention, and to the appended claims.
REFERENCES:
patent: 5937195 (1999-08-01), Ju et al.
patent: 6446258 (2002-09-01), McKinsey et al.
patent: 6591414 (2003-07-01), Hibi et al.
On Predicated Execution, HPL-91-58, May 1991, Joseph C.H. Park, Mike Schlansker, pp. 1-25.
Global Predicate Analysis and its Application to Register Allocation, IEEE 1996, 1072-4451/96, David M. Gillies, Dz-ching Roy Ju, Richard Johnson, and Michael Schlansker, pp. 114-125.
Swizzle barrier optimizations for orthogonal persistence in Java, presented at the Third International workshop on Persistence and Java, Aug. 17, 1998, pp. 1-14.
Static Single Assignment Form for Machine Code, Sigplan '99 (PLDI) 5/99, 1999 ACM 1-58113-083-X/99/0004, Allen Leung an Lal George, pp. 204-214.
Dynamic Optimization Infrastructure and Algorithms for IA-64, Kim Michelle Hazelwood, These presented to North Carolina State University, Master of Science, pp. 1-98.
Accurate and Efficient Predicate Analysis with Binary Decision Diagrams, IEEE 2000, 0-7695-0924, John W. Sias, Wen-mei W. Hwu and David I. August, pp. 112-123.
IA64 Software Conventions and Runtime Architecture, Document No. 245358-002, Sep. 2000, pp 11-1 to 11-18, See websitedeveloper.intelcom.
Chaiken Ronnie Ira
Gillies David Mitford
Grace Ryan T.
Kim Kenneth S.
Merchant & Gould
Microsoft Corporation
LandOfFree
Method for binary-level branch reversal on computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for binary-level branch reversal on computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for binary-level branch reversal on computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3273600