Method and apparatus for profile-based code placement using a mi

Details Method and apparatus for profile-based code placement using a mi Method and apparatus for profile-based code placement using a mi

1997-06-30

1999-11-02

Hafiz, Tariq R.

395708, G06F 945

Patent

active

059785888

ABSTRACT:
A method and apparatus placing blocks of object code by a compiler. The code placement is done optimally, using a "cut set technique" that uses the "max-flow/min-cut" principle. A preferred embodiment of the present invention divides a source program into blocks and generates a control flow graph (cfg) and a data flow graph (dfg) for the blocks. The compiler then identifies the strongly connected components (sccs) of the dfg and recursively breaks down the cycles in each scc to yield a plurality of directed acyclic graphs (dfg-dag's). The compiler then finds the "minimum cut set" in the cfg corresponding to each dfg-dag and moves the code into blocks in accordance with the minimum cut sets. Lastly, the compiler generates object code for the blocks.

REFERENCES:
patent: 5555201 (1996-09-01), Dangelo et al.
patent: 5557761 (1996-09-01), Chan et al.
patent: 5666296 (1997-09-01), Gafter
patent: 5787287 (1998-07-01), Bharadwaj
patent: 5850552 (1998-12-01), Odani et al.
patent: 5894576 (1999-04-01), Bharadwaj
Preston Briggs, Register Allocation Via Graph Coloring, PH.D. Thesis, Rice University, submitted Apr. 1992, obtained from UMI Dissertation Services: Ann Arbor, MI.
Raymond Lo, Sun Chan, Jim Dehnert, Ross Towle, "Aggregate Operation Movement: A Min-Cut Approach to Global Code Motion," Proceedings available from Springer Verlap, Aug. 26-29, 1996, 14 pages.
Pohua P. Chang, Scott A. Mahlke, Wen-Mei W. Hwu, Software-Practice and Experience, "Using Profile Information to Assist Classic Code Optimization," vol. 21(12), John Wiley & Sons, Ltd, Dec. 1991 pp. 1301-1321.
Jens Knoop, Oliver Ruthing Bernhard Steffen, "Lazy Code Motion, " Proceedings of SIGPLAN '92 Conference on Programming Language Design and Implementation, San Francisco, CA, Jun. 17-19, 1992.
Rajiv Gupta, Generalized Dominators and Post-dominators, ACM, copyright 1992.
Thomas Ball, James R. Larus, "Optimally Profiling and Tracing Programs," paper presented at 19.sup.th Annual ACM SIGNPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, pp. 59-70, Jan. 19-22, 1992.
Rahmouni, M.; Jerraya, A.; "Formulation and Evaluation of Scheduling Techniques for Control Flow Graphs"; Proceedings of EURO-DAC '95, European Design Automation Conference; pp. 386-391, Sep. 1995.
Kramer, R.; Gupta, R.; Soffa, M.; "The Combining DAG: A Technique for Parallel Data Flow Analysis"; IEEE Transactions on Parallel and Distributed Systems; vol. 5, Issue 8, pp. 805-813, Aug. 1994.
Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, "Compilers Principles, Techniques, and Tools", 1986.

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2147649