Data processing: software development – installation – and managem – Software program development tool – Translation of code
Patent
1997-10-22
2000-06-20
Lintz, Paul R.
Data processing: software development, installation, and managem
Software program development tool
Translation of code
395709, 395710, G06F 945
Patent
active
060773138
ABSTRACT:
Type partitioned dataflow analyses perform a dataflow analysis of a program by partitioning the dataflow analysis into phases using types to help reduce costs attendant to the dataflow analysis of the entire program. Each phase models only a subset of the relevant program quantities and may be analyzed separately. Type partitioned dataflow analyses extend quantity-based partitioning to non-separable dataflow analyses by determining analysis-time dependencies connoting potential run-time interactions between relevant program quantities and scheduling the dataflow analysis of each program quantity after the dataflow analysis of all other program quantities upon which it depends. Because each phase may be analyzed separately, type partitioned dataflow analyses may enable the use of suitable efficient dataflow techniques, such as suitable sparse representation methods for example, that otherwise could not have been used for an entire non-separable program and may also enable the performance of dataflow analyses in parallel for more than one separate phase of such a non-separable program.
REFERENCES:
patent: 5127104 (1992-06-01), Dennis
patent: 5146594 (1992-09-01), Iitsuka
patent: 5396627 (1995-03-01), Iitsuka
patent: 5465372 (1995-11-01), Gottlieb et al.
patent: 5485616 (1996-01-01), Burke et al.
patent: 5790866 (1998-08-01), Robison
patent: 5896537 (1999-04-01), Landi et al.
Johnson et al, "Dependence based program analysis", ACM SIGPLAN PLDI, pp. 78-89 Apr. 1993.
Diwan et al, Type based alias analysis, ACM SIGPLAN, pp. 106-117 Apr. 1998.
Grunwald et al, "Data flow equation for explictly parallel programs", ACM PPOPP pp. 159-168 May 1993.
Ramalingam, "Data flow frequency analysis", PLDI ACM, pp. 267-277 Feb. 1996.
Defouw et al, "Fast interprocedural class analysis", POPL ACM, pp. 222-236 Mar. 1998.
Reps et al., "Precise interprocedural dataflow analysis via graph reachability", POPL ACM, pp. 49-61 1995.
Lee and Ryder, "A comprehensive approach to parallel dataflow analysis", ICS ACM, pp. 236-247 1992.
Debray, "Effficient dataflow analysis of logic programs", J. of ACM, vol. 39, No. 4, Oct. 92, pp. 949-984, 1992.
Collard et al., "Fuzzy array dataflow analysis", PPOPP 95 ACM, pp. 92-101, 1995.
Horwitz et al., "Demand interprocedural dataflow analysis", SIGSOFT 95, ACM, pp. 104-115, 1995.
Maslov, "Enhancing array dataflow dependence analysis with on demand global value propagation", ICS 95 ACM, pp. 265-269, 1995.
Debray, "On the complexity of dataflow analysis of logic programs", ACM Tran. Prog. Lang. & Syst. vol. 17, No. 2, Mar. 1995, pp. 331-365.
Miller et al., "A quanitative analysis of locality in dataflow diagram", ACM, 1991 pp. 12-18.
Najjar et al., "Analysis of loop latency in dataflow execution", ACM 1992, pp. 352-360.
Ruf, "Partitioning dataflow analyses using types", POPL 97 ACM, pp. 15-26, 1997.
Jensen, "Clock analysis of synchronous dataflow programs", PEPM 95 ACM, pp. 156-167, 1995.
Chase, David R, et al., "Analysis of Pointers and Structures," Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation, White Plains, New York, pp. 296-310 (Jun. 20-22, 1990).
Choi, Jong-Deok, et al., "Automatic Construction of Sparse Data Flow Evaluation Graphs," Proceedings of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, pp. 55-66 (Aug. 1990).
Cousot, Patrick, et al., "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints," Proceedings of the Fourth Annual ACM Symposium on Principles of Programming Languages, pp. 238-252 (Jan. 1977).
Cytron, Ron, et al., "Efficiently Computing Static Single Assignment From and the Control Dependence Graph," ACM Transactions on Programming Language and System, vol. 13, No. 4, pp. 451-490 (Oct. 1991).
Deutsch, Alain, "Interprocedural May-Alias Analysis for Pointer: Beyond k-limiting," SIGPLAN'94 Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 230-241 (Jun. 1994).
Dhamdhere, Dhananjay M., et al., "How to Analyze Large Programs Efficiently and Informatively," Proceedings of the SIGPLAN'92 Conference on Programming Language Design and Implementation, pp. 212-223 (Jun. 1992).
Duesterwald, Evelyn, et al., "Reducing the Cost of Data Flow Analysis By Congruence Partitioning ," CC'94: Fifth International Conference on Complier Construction, pp. 357-373 (Apr. 1994).
Hendren, Laurie J., et al., "Abstractions for Recursive Pointer Data Structure: Improving the Analysis and Transformation of Imperative Programs," Proceedings of the SIGPLAN'92 Conference on Programming Language Design and Implementation, pp. 249-260 (Jun. 1992).
Henglein, Fritz, "Efficient Type Inference for Higher-Order Binding-Time Analysis," Functional Programming Language and Computer Architecture, 5th ACM Conference, Cambridge, Massachusetts, pp. 448-472 (Aug. 26-30, 1991).
Henglein, Fritz, "Global Tagging Optimization by Type Inference," Proceedings of the Conference on LISP and Functional Programming, pp. 205-215 (Jun. 1992).
Johnson, Richard, et al., "The Program Structure Tree: Computing Control Regions in Linear Time," Proceedings of the SIGPLAN'94 Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 171-185 (Jun. 20-24, 1994).
Jourdan, Martin, et al., "Techniques for Improving Grammar Flow Analysis," Lecture Notes in Computer Science, No. 432, 3rd European Symposium on Programming, Copenhagen, Denmark, pp. 240-255 (May 15-18, 1990).
Landi, William, et al., "Pointer-induced Aliasing: A Problem Classification," Proceedings of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, pp. 93-103 (Aug. 1990).
Landi, William, et al., "A Safe Approximate Algorithm for Interprocedural Pointer Aliasing," Proceedings of the SIGPLAN'92 Conference on Programming Language Design and Implementation, pp. 235-248 (Jun. 1992).
Lee, Yong-fong et al., "Region Analysis: A Parallel Elimination Method for Data Flow Analysis," International Conference on Computer Language, IEEE Computer Society, pp. 31-42 (May 1994).
O'Callahan, Robert, et al., "Detecting Shared Representations Using Type Inference," Technical Report CMU-CS-95-202, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, pp. 1-21 (Sep. 1995).
O'Callahan, Robert, et al. "Practical Program Understanding With Type Inference," Technical Report CMU-CS-96-130, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, pp. 1-18 (May 1996).
Reps. Thomas, et al., "Precise Interprocedural Dataflow Analysis via Graph Reachability," Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 49-61 (Jan. 1995).
Ruf, Erik, "Context-Insensitive Alias Analysis Reconsidered," SIGPLAN'95 Conference on Programming Language Design and Implementation, La Jolla, California, pp. 13-22 (Jun. 1995).
Ruf, Erik, "Optimizing Sparse Representations for Dataflow Analysis," ACM SIGPLAN Workshop on Intermediate Representations(IR'95), San Francisco, California, pp. 50-61 (Jan. 1995).
Steensgaard, Bjarne, "Sparse Functional Stores for Imperative Programs," ACM SIGPLAN Workshop on Intermediate Represntations (IR'95), San Francisco, California, pp. 62-70 (Jan. 22, 1995).
Steensgaard, Bjarne, "Points-to Analysis in Almost Linear Time," Proceedings of the 23rd SIGPLAN/SIGACT Symposium on Principles of Programming Languages, St. Petersburg, Florida, pp. 32-41 (Jan. 21-24, 1996).
Steensgaard, Bjarne, "Points-to Analysis by Type Inference of Programs with Structures and Unions," Lecture Notes on Computer Science, vol. 1060, Proceedings of the 1996 International Conference on Compiler Construction, Linkobing, Sweden, pp. 136-150 (Apr. 24-26, 1966).
Weise, Daniel, et al., "Value Dependence Graphs: Representation Without Taxation," Technical Report MSR-TR-94-03, Microsoft Research, Redmond, Washington, 14 pages (Apr. 13, 1994).
Wilson, Robert P., et al., "Efficient Context-Sensitive Pointer Analysis for C Programs," SIGPLAN'95 Conference on Programming Language Design and Implementa
Khatri Anil
Lintz Paul R.
Microsoft Corporation
LandOfFree
Type partitioned dataflow analyses does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Type partitioned dataflow analyses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Type partitioned dataflow analyses will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1848410