POPL 1996: St. Petersburg Beach, 1996
We present m interprocedural flow-lnsensltlve points-to rmalysls based on type ]nference methods with an almost hneart ime cost complexity To our knowled~e, this is the asymptotically fastest non-trlwzd lnterprocedural points-to analysis algorlthm ...
4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, 1977
A program denotes computations in some universe of objects. Abstract interpretation of programs consists in using that denotation to describe computations in another universe of abstract objects, so that the results of abstract execution give some ...
Jong-Deok Choi, Michael G. Burke, Paul R. Carini
20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1993
We present practical approximation methods for computing interprocedural aliases and side effects for a program written in a language that includes pointers, reference parameters and recursion. We present the following results: 1) An algorithm for ...
This paper describes proof-carrying code (PCC), a mechanism by which a host system can determine with certainty that it is safe to execute a program supplied (possibly in binary form) by an untrusted source. For this to be possible, the untrusted ...
L. Peter Deutsch, Allan M. Schiffman
11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, 1984
The Smalltalk-80* programming language includes dynamic storage allocation, full upward funargs, and universally polymorphic procedures; the Smalltalk-80 programming system features interactive execution with incremental compilation, and ...
Thomas W. Reps, Susan Horwitz, Mooly Sagiv, Shmuel Sagiv
POPL 1995: San Francisco, 1995
The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow ...
In order to analyze a program that involves pointers, it is necessary to have (safe) information about what each pointer points to. There are many different approaches to computing points-to information. This paper addresses techniques for flow- and ...
D.J. Kuck, Robert H. Kuhn, D. Padua, Bruce Leasure, Michael Wolfe
8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1981
Dependence graphs can be used as a vehicle for formulating and implementing compiler optimizations. This paper defines such graphs and discusses two kinds of transformations. The first are simple rewriting transformations that remove dependence arcs. ...
6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, 1979
Semantic analysis of programs is essential in optimizing compilers and program verification systems. It encompasses data flow analysis, data type determination, generation of approximate invariant assertions, etc.
This paper is concerned with the polymorphic type discipline of NL, which is a general purpose functional programming language, although it was first introduced as a metalanguage (whence its name) for conducting proofs in the LCF proof ...