Expanding a software program by insertion of statements

Details Expanding a software program by insertion of statements Expanding a software program by insertion of statements

2007-04-17

2007-04-17

Nguyen-Ba, Antony (Department: 2192)

Data processing: software development, installation, and managem

Software program development tool

Code generation

C717S114000, C717S140000, C717S151000, C717S144000, C717S156000

Reexamination Certificate

active

10402663

ABSTRACT:
Every function that is called (“called function”) is expanded by insertion of several statements at the entry and exit thereof. Moreover, a calling function may also be expanded, by insertion of statements prior to and/or subsequent to a statement in which a called function is invoked. Many of the statements that are inserted contain new variables (called “synthetic variables”) to which registers are allocated during register allocation; the synthetic variables are not part of the originally-written software but are introduced during expansion, e.g. to transfer arguments to and return value from the called functions. Statements that are inserted can be either statements that are translated into assembly code in the normal manner, or alternatively dummy statements that contain instructions which are never translated into assembly code (i.e. ignored by the assembler. Use of dummy statements ensures that a web is established for new variables. After expansion, register allocation is performed.

REFERENCES:
patent: 4571678 (1986-02-01), Chaitin
patent: 4656582 (1987-04-01), Chaitin et al.
patent: 4777588 (1988-10-01), Case et al.
patent: 4782444 (1988-11-01), Munshi et al.
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5428793 (1995-06-01), Odnert et al.
patent: 5530866 (1996-06-01), Koblenz et al.
patent: 6553426 (2003-04-01), Holzle et al.
patent: 2004/0003385 (2004-01-01), Kushlis
Boquist-Johnson, The GRIN Project: A Highly Optimising Back End for Lazy Functional Languages, 1995, Chalmers University of Technology, Department of Computing Science, Goteborg, Sweden, {boquist, johnson}@cs.chalmers.se.
Entire File History of U.S. Appl. No. 10/402,736, filed on Mar. 28, 2003 by G. Verbitsky, including all office actions and amendments therein.
Urban Boquist, “Interprocedural Register Allocation for Lazy Functional Languages”, Licentiate Degree Dissertation, Computer Science, Chalmers University of Technology, Goteborg, Sweden, Mar. 13, 1995.
P. Briggs, K. D. Cooper, K. Kennedy, and L. Torczon, “Coloring Heuristics for Register Allocation”, in Proceedings of the ACM SIGPLAN, Conference on Programming Language Design and Implementation, pp. 275-284, Portland, Oregon, Jul. 1989.
“Register Allocation”, Chapter 16 of the book “Advanced Compiler Design and Implementation” by Steven S. Muchnick, published by Morgan Kaufmann, Academic Press 1997.
P. Briggs, K. Cooper, and L. Torczon, “Coloring Register Pairs,” ACM Letters on Programming Languages and Systems, 1(1):3-13, Mar. 1992.
M. D. Smith, and G. Holloway, “Graph-Coloring Register Allocation for Architectures with Irregular Register Resources”, Submitted to PLDI, 2002.
Timothy Kong, Kent D. Wilken, “Precise Register Allocation for Irregular Architectures,” International Symposium on Microarchitecture, 1998.
Preston Briggs, Keith D.Cooper, Linda Torczon, “Improvements to Graph Coloring Register Allocation”, ACM Transactions on Programming Languages and Systems, 1994.
Nickerson, “Graph coloring register allocation for processors with multi-register operands”, 1990 (pp. 40-52).
Michael D. Smith & Glenn Holloway, “Graph-Coloring Register Allocation for Irregular Architectures” 2001.
Mogensen, “Register allocation for 8-bit processors?”, Mar. 1995 in “comp.compilers” News Group.
Preston Briggs, “Register Allocation via Graph Coloring”, PhD Thesis, Rice University, Apr. 1992.
Neighborhood-based Variable Ordering Heuristics for the Constraint Satisfaction Problem by gbessiere et al 2001 (5 pages).
A Faster Optimal Register Allocator, Fu et al. IEEE Jan. 2002, pp. 245-256.
The GRIN Project: A Highly Optimizing Back End for Lazy Functional Languages, Boquist-Johnson, 1995, Chalmers University of Technology, Department of Computing Science, Goteborg, Sweden.

Affiliated with

Also associated with

Rating

Expanding a software program by insertion of statements does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Expanding a software program by insertion of statements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expanding a software program by insertion of statements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3741897