Method and apparatus for conflict-based block reordering

Details Method and apparatus for conflict-based block reordering Method and apparatus for conflict-based block reordering

1997-06-18

1999-08-03

Hafiz, Tariq R.

395580, 395581, G06F 945

Patent

active

059336447

ABSTRACT:
A method and apparatus for ordering blocks of code by a compiler. The compiler generates a conflict graph in accordance with the blocks of a computer program being compiled. Once the conflict graph is generated, a preferred embodiment of the present invention finds maximum weight independent set (MWS) of nodes in the conflict graph. By definition, the nodes in the MWS have no flow control conflicts between them. The compiler then generates an object program having blocks ordered in accordance with the maximum weight independent set.

REFERENCES:
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5659754 (1997-08-01), Grove et al.
patent: 5774730 (1998-06-01), Aizikowitz et al.
patent: 5787284 (1998-07-01), Blainey et al.
patent: 5790858 (1998-08-01), Vogel
patent: 5797012 (1998-08-01), Blainey et al.
Karl Pettis et al. "Profile Guided Code Positioning," Proceedings of the ACM SIGPLAN '90 Conference On Programming Language Design and Implementation, Jun. 20-22, 1990, Sigplan Notices vol. 25, No. 6, pp. 16-27.
Wen-mei W. Hwu et al. "Achieving High Instruction Cache Performance with an Optimizing Compiler," Proceedings of The 16th Annual International Symposium on Computer Architecture, IEEE, 1989, pp. 242-251.
Brad Calder et al. "Reducing Branch Costs via Branch Alignment," ACM, ASPLOS V1, 1994, pp. 242-251.
Thomas Ball et al. "Optimally Profiling and Tracing Programs," ACM Transactions on Programming Languages and Systems, vol. 16, No. 4, Jul. 1994, pp. 1320-1360.

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-858702