Data flow analysis of communicating processes
Published 1 January 1979Open access
John H. Reif
Citations26
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper extends flow analysis techniques developed for sequential programs to the analysis of communicating, concurrent processes.
Abstract
Data flow analysis is a technique essential to the compile-time optimization of computer programs, wherein facts relevant to program optimizations are discovered by the global propagation of facts obvious locally.This paper extends flow analysis techniques developed for sequential programs to the analysis of communicating, concurrent processes.
Keywords
Computer Science
SIAM Journal on ComputingDepth-First Search and Linear Graph Algorithms
6,021 Citations1972Robert E. Tarjan
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples of an improved version of an algorithm for finding the strongly connected components of a directed graph.
Annals of MathematicsRecursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines
703 Citations1961Marvin Minsky
The main results of this paper show that the same notions of computability can be realized within the highly restricted monogenic formal systems called by Post the "Tag" systems, and within a peculiarly restricted variant of Turing machine which has two tapes, but can neither write on nor erase these tapes.
Acta InformaticaMonotone data flow analysis frameworks
380 Citations1977John B. Kam, Jeffrey D. Ullman
This work shows the nonexistence of an algorithm to compute the meet over all paths solution for monotone frameworks, and shows that the maximal fixed point solution exists for every instance of everymonotone framework, and that it can be obtained by Kildall's algorithm.
Journal of the ACMA Fast and Usually Linear Algorithm for Global Flow Analysis
187 Citations1976Susan L. Graham, Mark N. Wegman
A new algorithm for global flow analysis on reducible graphs which has a worst-case time bound of O(e log e) function operations and a restriction to one-entry one-exit control structures guarantees linearity.
ACM Computing SurveysConcurrent Programming Concepts
151 Citations1973Per Brinch Hansen
The evolution of language features for multiprogramming from event queues and semaphores to critical regions and monitors is described and it is suggested that the choice of language concepts should be guided by two simple principles.
IEEE Transactions on Software EngineeringProperty extraction in well-founded property sets
93 Citations1975Ben Wegbreit
Techniques are presented for property computation in iterative and recursive programs and application to a variety of property sets is discussed.
Analysis of a simple algorithm global data flow problems
77 Citations1973Matthew S. Hecht, Jeffrey D. Ullman
There is an ordering of the nodes of a flow graph G which topologically sorts the dominance relation and can be found in 0(edges) bit vector steps and it follows that there is a very simple bit propagation algorithm which also uses the above ordering, and is at least as good as the interval algorithm for solving all known global data flow problems.
ACM SIGPLAN NoticesPreliminary ZENO language description
5 Citations1979John E. Ball, Graeme Williams +1 more
The specification of ZENO, a programming language intended as the target language for a research project in advanced compiling, is presented and is strongly based on EUCLID, with modifications for message-based parallel processing and a somewhat different treatment of data types.