Method and apparatus for elimination of redundant branch instruc

Electrical computers and digital processing systems: processing – Processing architecture – Distributed processing system

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

395708, 712234, G06F 945

Patent

active

059997397

ABSTRACT:
The procedure of the invention eliminates redundant conditional branch statements (CBSs) from a program, wherein the program includes (i) plural blocks of program statements, (ii) a definition statement (DEF) for each variable in the program that assigns a value to each variable, (iii) a defining point (DEFP) which is a first point in the program that a value is calculated, and (iv) plural CBSs. Each CBS transfers control to one of two target blocks of program statements, dependent upon an operation code and controlling variable that form a part of the test associated with the CBS. The procedure associates all DEFs which define a same value, with a DEFP for the same value and determines (i) a controlling variable upon which a test CBS is dependent, (ii) a DEF of the controlling variable of the test CBS and (iii) a DEFP for the DEF of the controlling variable. If a value first calculated at the DEFP found in (iii) is utilized by a CBS, the procedure finds which arm of the CBS reaches the test CBS; and then revises a block of program statements that include the test CBS, to eliminate at least a test required by the test CBS, and replace the conditional branch with an unconditional branch.

REFERENCES:
patent: 5202995 (1993-04-01), O'Brien
patent: 5511198 (1996-04-01), Hotta
patent: 5923883 (1999-07-01), Tanaka et al.
"Global Value Numbers and Redundant Computations", Rosen et al., Proc. 15th ACM SIGACT-SIGPLAN Symposium on Programming Languages (Jan., 1988) pp. 12-27.
"Compact Representations of Control Dependence", Cytron et al. Proc. ACM SIGPLAN '90 Symposium on Programming Language Design . . . (Jun., 1990) pp. 337-351.
"Constant Propagation with Conditional Branches", Wegman et al., ACM Trans. on Programming Languages . . . , V 13, No. 2, Apr. 1991, pp. 181-210.
Choi, S.-U.; Par, S.-S.; Park, M.-S.; "Eliminating Conditional Branches for Enhancing Instruction Level Parallelism in VLIW Compiler"; Proceedings, Second International Symposium on Parallel Architectures, Algorithms, and Networks; pp. 193-199, Jun. 1996.
Mueller, F.; Whalley, D.; "Avoiding Conditional Branches by Code Replication"; ACM SIGPLAN Notices; vol. 30, No. 6, pp. 56-66, Jun. 1995.
Bacon, D.; Graham, S.; Sharp, O.; "Compiler Transformations for High-Performance Computing"; ACM Computing Surveys; vol. 26, No. 4, pp. 345-420, Dec. 1994.
Briggs, P.; Cooper, K.; "Effective Partial Redundancy Elimination"; Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementaion; pp. 159-170, 1994.
"Branch Replacement Optimizations for Trace Directed Program Restructuring"; IBM Technical Disclosure Bulletin; vol. 36, No. 9B, pp. 557-558, Sep. 1993.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for elimination of redundant branch instruc 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 and apparatus for elimination of redundant branch instruc, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for elimination of redundant branch instruc will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-834242

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.