Boots – shoes – and leggings
Patent
1993-10-12
1996-01-16
Kriess, Kevin A.
Boots, shoes, and leggings
364DIG1, 3642805, 3642804, G06F 944
Patent
active
054856167
ABSTRACT:
By novel use of the Program Call Graph representation of computer programs, this method and apparatus provides a general analysis method for interprocedural bidirection data flow problems in computer software programs. The invention has many uses, including the determination of interprocedural alias analysis of computer software programs which contain pointers.
The method starts by constructing a Program Call Graph representation of a computer program with each node of the graph representing a routine of the program. An internal representation of each node is then constructed and initial interprocedural values are associated with appropriate nodes. An interprocedural traversal of the Program Call Graph is performed in which each node is visited; an intraprocedural propagation is performed to develop a new set of interim solution values; and the new interim solution values are interprocedurally propagated. The new interim solution is propagated in a forward and backward direction in one pass of the traversal. The interprocedural traversal of the Program Call Graph is repeated until the interprocedural solution does not change.
REFERENCES:
patent: 4503492 (1985-03-01), Pilat
patent: 4893234 (1990-01-01), Davidson et al.
patent: 4922414 (1990-05-01), Holloway et al.
patent: 5107418 (1992-04-01), Cramer et al.
patent: 5161216 (1992-11-01), Reps et al.
patent: 5170465 (1992-12-01), McKeeman et al.
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5182806 (1993-01-01), McKeeman et al.
patent: 5327561 (1994-07-01), Choi et al.
Burke, Michael & Barbara G. Ryder, "A Critical Analysis of Incremented Iterative Data Flow Analysis Algorithms", IEEE Jul. 1990.
Marlowe, Thomas J. & Ryder, Barbara G., "Hybrid Incremental Alias Analysis", 1991 IEEE.
Banning, J., Sixth Annual ACM Symposium on Principles of Programming Languages, (Jan. 1979) pp. 29-41.
Cooper, et al, SIGPLAN '88 Conference on Programming Language Design and Implementation (Jun. 1988) pp. 57-66.
Callahan, D., Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, (Jun. 1988) pp. 47-56.
Landi & Ryder, Eighteenth Annual ACM Symposium on Principles of Programming Languages, Jan. 1991 pp. 93-103.
Harold and Soffa, Proceedings of the IEEE Computer Society 1990 International Conference on Computer Languages, (1990) pp. 297-306.
Landi & Ryder, SIGPLAN '92 Conference on Programming Language Design and Implementation pp. 235-248. (Jun. 1992).
J. Ferrante, K. Ottenstein "The Program Dependence Graph and Its Use In Optimization" IBM Technical Report RC-10543 Jun. 1984 Computer Science pp. 1-33.
L. Gurevich, Harel & Rubin, "Computing the Aliasing Relation" IBM TDB Jan. 1986 pp. 3503-3508.
K. Gilbert, "Effective Register Management During Code Generation" Jan. 1973 IBM TDB pp. 2640-2645.
ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, San Francisco, Calif., vol. 27 No. 7 Jul. 1992 (ABSTRACT).
L. J. Hendren, J. Hummel, A. Nicolau "Abstractions for Recursive Pointer Data Structures: Improving the Analysis and Transformation of Imperative Programs" SIGPLAN Not.USA vol. 27, No. 7, pp. 249-260 Jul. 1992 (ABSTRACT ).
J. Crowcroft, I. Wakeman, Z. Wang, D. Sirovica, "Is Layering, Harmful?" (Remote Procedure Call) IEEE Netw. (USA) vol. 6,. No. 1, Jan. 1992, pp. 20-24 (ABSTRACT).
Yi-Hsiu Wei, A. Stoyenko, G. Goldszmidt "The Design of a Stub Generator for Heterogeneous RPC Systems" J. Parallel Distrib. Comput. USA, vol. 11, No. 3, pp. 188-197 Mar. 1991 (ABSTRACT).
A. Ah-kee "Proof Obligations for Blocks and Procedures" Form. Asp. Comput. UK, vol. 2, No. 4, pp. 312--330, Oct.-Dec. 1990 (ABSTRACT).
E. G. Wagner et al., "On Declarations" Categorical Methods in Computer Science With Aspects from Topology, Springer-Verlag, Vi+350 pp. 261-267, 1989 (ABSTRACT).
D. R. Chase, M. Wegman, F. Zadeck, "Analysis of Pointers and Structures" SIGPLAN Not. (USA), vol. 25, No. 6, pp. 296-310, Jun. 1990 (ABSTRACT).
L. Beliard, "Microsoft C 6.0: The New-Generation C" Micro Syst. (France) No. 109, pp. 105-111, Jun. 1990 (Journal Paper) (ABSTRACT).
S. Richardson, M. Ganapathi "Code Optimization Across Procedures" Computer (USA), vol. 22, No. 2, pp. 42-50, Feb. 1989 (ABSTRACT).
H. Dietz, C-H Chi, "CRegs: A New Kind of Memory for Referencing Arrays and Pointers" Proceedings. Supercomputing '88 IEEE Comput. Soc. Press, xii+458 pp. 360-367 (ABSTRACT).
M. L. Scott et al., "Design Rationale for Psyche, A General Purpose Multiprocessor Operating System" Proceedings Penn State U (xii+461+462x+262xiii+311) pp. 255-262 vol. 2 1988. (ABSTRACT).
V. A. Guarna, F. Briggs, Conference Paper Proceedings, 1988 International Conference on Paralel Processing (xiii+461+X+262+xiii+311) pp. 212-220 vol. 2, 1988 (ABSTRACT).
J. R. Larus, P. Hilfinger, "Detecting Conflicts Between Structure Accesses" SIGPLAN Not. (USA) vol. 23, No. 7, pp. 21-34, Jul. 1988 (ABSTRACT).
J. P. Jacky, I. J. Kalet, "An Object-Oriented Programming Discipline for Standard Pascal" Commun. ACM(USA), vol. 30. No. 9, 772-776, Sep. 1987 (ABSTRACT ).
R. B. Essick, IV, "Cross-Architecture Procedure Call", RPT. No. UIUCDCS-R-87-1340, v+144 pp. May 1987 (ABSTRACT).
D. A. Price, P. C. Poole, "Dynamic Data Flow Analysis--A Tool for Reliability" Instn. Eng. Australia, Barton, ACT, Aust. pp. 97-100, Feb. 1986 (ABSTRACT).
M. Burke, R. Cytron "Interprocedural Dependence Analysis and Parallelization" Dept. of Comput. Sci., IBM TJW Res. Center, Yorktown vol. 21, No. 7, pp. 162-175 Jul. 1986 Conference Paper (ABSTRACT).
K. D. Cooper, K. Kennedy, "Efficient Computation of Flow Insensitive Interprocedural Summary Information" SIGPLAN 84' vol. 19, No. 6, pp. 247-258, Jun. 1984 (ABSTRACT).
S. Walters, "The Advanced Architecture of the Z8 Microcomputer" Electron. Conventions, El Segundo, Calif., USA pp. 26-3/1-12, 1981 Conf. Paper (ABSTRACT).
A. L. Chow, A. Rudmik "The Design of a Data Flow Analyzer" SIGPLAN 82' vol. 17, No. 6, pp. 106-113, Jun. 1982 Conf. Paper (ABSTRACT).
G. Barth, "Aliasing in Interprocedural Data Flow Analysis" Fachbereich Informatik, Germany, No. 43, pp. 275-286, 1981 (ABSTRACT).
R. Cartwright, D. Oppen, "The Logic of Aliasing" Journal Paper Acta Inf. (Germany), vol. 15, No. 4, pp. 365-384, Aug. 1981 (ABSTRACT).
D. H. Uyeno, W. Vaessen, "PASSIM: A Discrete-Event Simulation Package for PASCAL Simulation" Journal Paper Simulation (USA), vol. 35, No. 6, pp. 183-190, Dec. 1980 (ABSTRACT).
F. T. Bradshaw et al., "Procedure Semantics and Language Definition" SIGPLAN Not. (USA), vol. 15, No. 6, pp. 28-33, Jun. 1980 (ABSTRACT).
R. L. Schwartz, "Aliasing Among Pointers in EUCLID" Inf. Process. Lett. (Netherlands), vol. 9, No. 2, pp. 76-79, Aug. 1979 Jour. Paper (ABSTRACT).
D. B. Lomet, "Data Flow Analysis in the Presence of Procedure Calls" IBM Research & Dev. USA, vol. 21, No. 6, pp. 559-571, Nov. 1977 (ABSTRACT).
T. Yamamoto "A Scan Conversion Algorithm Using Quad-Tree Rerpsentation of dZ Buffer" Syst. Comput. Jpn. USA, vol. 23, No. 8, pp. 65-74 1992 (ABSTRACT).
A. W. Appel, Zhong Shao, "Callee-save Registers in Continuation-Passing Style" LISP Symb. Comput. (Netherlands) vol. 5, No. 3, pp. 191-221 Sep. 1992 (ABSTRACT).
P. Emma, J. Pomerene "Conditional Execution in a Register Management Scheme for Out of Sequence Execution" IBM TDB n10A Mar. 1992 pp. 449-454.
Burke Michael G.
Carini Paul R.
Choi Jong-Deok
International Business Machines - Corporation
Kriess Kevin A.
Pecello Louis J.
LandOfFree
Using program call graphs to determine the maximum fixed point s does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Using program call graphs to determine the maximum fixed point s, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using program call graphs to determine the maximum fixed point s will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-317221