Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-06-03
1998-09-22
Voeltz, Emanuel Todd
Data processing: database and file management or data structures
Database design
Data structure types
395707, 395708, 707 10, 707103, 707203, G06F 945
Patent
active
058128557
ABSTRACT:
The present invention provides a system and method for solving interprocedural problems on incomplete call graphs. For a given program, the present invention constructs a standard call graph on which the edges are updated with summary information needed to solve a given interprocedural problem such as constant propagation. Each node of the call graph having an unknown incoming edge is cloned. The call graph is then updated so that the unknown incoming edges are directed to the clone nodes and the known edges are directed to the original nodes. This results in a purified call graph on which an interprocedural problem can be solved. The present invention then creates a real clone of the procedure associated with each clone node of the call graph. The real clones are optimized according to the interprocedural solution. The present invention updates the known procedure calls of the program to call the real clones. Therefore, known procedure calls take advantage of optimized code, while unknown procedure calls continue to call unoptimized code.
REFERENCES:
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5179702 (1993-01-01), Spix et al.
patent: 5457799 (1995-10-01), Srivastava
patent: 5644709 (1997-07-01), Austin
patent: 5655122 (1997-08-01), Wu
Edinburgh Portable Compilers Ltd. "EPC Modula-2" from http://www.epc.co.uk/em2.html, 1997.
Marlowe, et al. "Hybrid incremental alias algorithms", IEEE, pp. 428-437, 1991.
Chow, "Minimizing register usage penalty at procedure calls", ACM Press, Proc. of the SIGPLAN'88 Conf. on Programming Language, pp. 85-94, Jun. 1988.
Cooper, et al., "The impact of interprocedural analysis & optimizations in R.sup.n programming environment", pub. in ACM Trans. on programming languages & syst, Oct. 1986.
Ferrante, et al., "The program dependence graph and its use in optimization", IBM Technical Report RC-10543, Computer Science, pp. 1-33, Jun. 1984.
Triolet, "Interprocedural analysis based restructuring of programs", Proc. on the international workshop on parallel algorithms & architectures; pub. by North-Holland, pp. 203-217, Apr. 1986.
Kuck, et al. "Dependence graphs and compiler optimizations", 8th annual ACM Symposium on principles of programming languages, (POPL), pp. 207-218, Jan. 1981.
Lomet, "Data flow analysis in the presence of procedure calls", pp. 559-571, Nov. 1977.
Hiranandani Seema
Ho Wingsturn Wilson
Nguyen Cuong H.
Silicon Graphics Inc.
Todd Voeltz Emanuel
LandOfFree
System and method for constaint propagation cloning for unknown does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for constaint propagation cloning for unknown , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for constaint propagation cloning for unknown will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1633817