Optimizing compiler with static prediction of branch probability

Details Optimizing compiler with static prediction of branch probability Optimizing compiler with static prediction of branch probability

1995-04-05

1997-08-05

Oberley, Alvin E.

395586, 395707, 395709, G06F 945

Patent

active

056551223

ABSTRACT:
A compiler and method for optimizing a program based on branch probabilities, branch frequencies and function frequencies. A number of algorithms executed by the compiler determine statically from the program code the probabilities that branches with the program are taken and how often the branches are taken. With this information, the compiler arranges the object code in memory to improve execution of the program. The frequency of functions within the code may be determined from the branch probability and branch frequency information. The compiler uses the function frequency information to arrange the functions in a desirable order, such as storing function pairs with the highest global call frequencies on the same memory page. This minimizes the number of calls to functions that are stored on disk and thus improves the speed of execution of the program.

REFERENCES:
patent: 5170465 (1992-12-01), McKeeman et al.
patent: 5457799 (1995-10-01), Srivastava
Ball, Thomas, and James R. Larus, "Optimally Profiling and Tracing Programs," Conference Record of the Nineteenth ACM Symposium on Principles of Programming Languages (Jan., 1992), pp. 59-70.
Ball, Thomas, and James R. Larus, "Branch Prediction for Free," Proceedings of ACM SIGPLAN'93 Conference on Programming Language Design and Implementation (Jun., 1993), pp. 300-313.
Forman, Tra R., "On the Time Overhead of Counters and Traversal Markers," Proceedings of the 15th International Conference on Software Engineering, Mar. 1981, pp. 164-169.
Graham, S.L., P.B. Kessler, and M.K. McKusick, "An Execution Profiler for Modular Programs," Software--Practice and Experience, 13, pp. 671-685 (1983).
Hall, M.W. and Ken Kennedy, "Efficient Call Graph Analysis," ACM Letters on Programming Languages and Systems, vol. 1, No. 3, Sep. 1992, pp. 227-242.
Hickey, T. and Choen, J., "Automating Program Analysis," JACM, 35, 1, 1988, pp. 185-220.
Ramamoorthy, C.V., "Discrete Markov Analysis of Computer Programs," In ACM Proceedings 20th National Conference, pp. 386-391, Aug. 1965.
Shafer, G, A Mathematical Theory of Evidence, Princeton, NJ: Princeton University Press, 1976.
Wagner, T.A., V. Maverick, S.L. Graham, and M.A. Harrison, "Accurate Static Estimators for Program Optimization," To appear: SIGPLAN PLDI '94, Jun. 1994.
Wall, David W., "Predicting Program Behavior Using Real or Estimated Profiles," Proceedings of ACM SIGPLAN '91 Conference on Programming Language Design and Implementation. Toronto, Ontario, Canada (Jun., 1991), pp. 59-70.

Affiliated with

Also associated with

Rating

Optimizing compiler with static prediction of branch probability does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimizing compiler with static prediction of branch probability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing compiler with static prediction of branch probability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1081843