Method for removing invariant branches from instruction loops of

Details Method for removing invariant branches from instruction loops of Method for removing invariant branches from instruction loops of

1992-09-03

1993-04-13

Lee, Thomas C.

Boots, shoes, and leggings

364DIG1, 3642805, 364DIG2, 364973, G06F 1538

Patent

active

052029956

ABSTRACT:
Removal of invariant branches from nests of loops results in an optimized computer program with increased speed of execution. To accomplish this objective, each loop of a program is then examined, looking at inner loops before their containing outer loops, to locate conditional branch instructions which are loop invariant. Each conditional branch which is evaluated based upon loop invariant calculations is rewritten, outside the outermost loop for which this branch is invariant. The moved branch is modified to branch around the loop in which it was originally contained if its condition is evaluated false. A new copy of the loop is made in which the invariant branch is rewritten as an unconditional branch. In the original copy of the loop, the invariant branch is deleted, and a branch is inserted after the modified original loop to skip around the new copy when the original copy is executed. Finally, any sections of the program which will never be executed as a result of the above described transformation are deleted.

REFERENCES:
patent: 4567574 (1986-01-01), Saade et al.
patent: 4656582 (1987-04-01), Chaitin et al.
patent: 4656583 (1987-04-01), Auslander et al.
patent: 4773007 (1988-09-01), Kasada et al.
patent: 4991088 (1991-02-01), Kam
Henhapl et al. "Parallel Loop Structures" IBM Technical Disclosure Bulletin vol. 16, No. 4, Sep. 1973 pp. 1047-1049.
Kizis, "Loopable Code Enhancement For An Ate Compiler" IBM Technical Disclosure Bulletin, vol. 25, No. 11B, Apr. 1983 pp. 6085-6089.
A. K. Chandra, "Identifying Inner Loops Of Programs" IBM Technical Disclosure Bulletin, vol. 18, No. 10, Mar. 1976 pp. 3514-3515.
P. F. Carpenter et al. "Program Optimization Technique" IBM Technical Disclosure Bulletin, vol. 12, No. 6, Nov. 1969, pp. 891-893.
F. E. Allen et al. "A Catalogue of Optimizing Transformations" IBM T. J. Watson Research Center Yorktown Heights, New York, 1972.
Robert Tarjan "Depth-First Search and Linear Graph Algorithms" Siam J. Comput. vol. 1, No. 2, Jun. 1972 pp. 146-160.
Barrett et al., "Compiles Construction: Theory and Practice," Science Research Associates, Inc., Chicago, 1979, pp. 551-587.
Bauer et al., "Compiler Construction an Advanced Course," 2nd ed., Springer-Verlag, New York, 1976, pp. 549-603.
Gries, David, "Compiler Construction For Digital Computers," John Wiley and Sons, New York, 1971, pp. 376-411.
Lewis et al., "Compiler Design Theory," Addison-Wesley, Mass., 1976, pp. 559-569.

Affiliated with

Also associated with

Rating

Method for removing invariant branches from instruction loops of 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 removing invariant branches from instruction loops of, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for removing invariant branches from instruction loops of will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1161534