Electrical computers and digital processing systems: processing – Processing architecture – Distributed processing system
Patent
1997-11-18
1999-12-07
Hafiz, Tariq R.
Electrical computers and digital processing systems: processing
Processing architecture
Distributed processing system
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.
Ayers Andrew
Soni Vineet
Hafiz Tariq R.
Hewlett--Packard Company
Sattizahn Brian
LandOfFree
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.
Profile ID: LFUS-PAI-O-834242