In this paper we study the profitability of applying the "reduction in strength" technique to programs in set-theoretic languages, focusing on the high level constructs involving set-formers. We define recursively two classes of expressions we shall call inductively computable set-formers and inductively computable predicates which can be evaluated with an order of magnitude improvement of the asymptotic running time as compared to the straightforward evaluation. The quantity developed for this comparison can be used to derive further results when additional information is known. For programs written in very high level languages, which often consist mostly of "nested" iterative constructs, this technique amounts to altering the "algorithm" used to compute the program by replacing it with an asymptotically faster algorithm.

We propose a new optimization technique applicable to set-oriented languages, which we shall call general common subexpression elimination. It involves the computation of the IAVAIL(n) function for all nodes n in a flow graph, where IAVAIL(n) is the set of expressions such that along every path leading to n, there will be found a computation of the expression followed by only incidental assignments (i.e. A = A ∪ {x} or A = A - {x}) to its operands and that the number of such assignments is bounded, independent of the path taken. We shall try to justify our definitions and demonstrate the usefulness of this technique by several examples. We shall show that this optimization problem does not fit into the semilattice-theoretic model for global program optimization [Ki, KU, GW], and that the standard iterative algorithm for such problems does not work in this case. We then give several theorems which allow the problem to be solved for reducible flow graphs. The formulae given in the theorems are in such a form that an efficient algorithm can be found by adapting an algorithm given in [U]. The resulting algorithm takes 0(e log e) steps of an extended type, where bit vector operations are regarded as one step, and e is the number of edges of the flow graph. It takes 0(n log n) extended steps for a program flow graph of n nodes.

We explore the notion of an induction variable in the context of a set-theoretic programming langugage. An appropriate definition, we believe, involves both the necessity that changes in the variable around a loop be easily computable and that they be small. We attempt to justify these requirements and show why they are independent assumptions. Next the question of what operators on sets play the role of +, − and * for arithmetic languages is explored, and several theorems allowing us recursively to detect induction variables in a loop are given. It is shown that most of the usual set operations do fit nicely into the theory and help form induction variables. The reason most variables fail to be induction variables concerns the structure of control flow, more than it does the operators applied.

The depth of a flow graph is the maximum number of back edges in a cycle free path, where a back edge is defined by some depth-first spanning tree for the flow graph. In the case of a reducible graph, the depth is independent of the DFST chosen. We show that the computation of the depth of a reducible flow graph may be done in polynomial time. Our algorithm is 0(ne) on a flow graph of n nodes and e edges. Since e≤2n for normal flow graphs, our algorithm is really 0(n2). While even an 0(n2) algorithm is not likely to be acceptable, it is suggestive of the possibility of a more efficient algorithm. Finally, we show that the general problem of computing the depth of an arbitrary flow graph with respect to an arbitrary DFST is NP-complete.

Article Free Access Share on Application of lattice algebra to loop optimization Authors: Amelia Fong Princeton University, Princeton N. J. Princeton University, Princeton N. J.View Profile , John Kam Princeton University, Princeton N. J. Princeton University, Princeton N. J.View Profile , Jeffrey Ullman Princeton University, Princeton N. J. Princeton University, Princeton N. J.View Profile Authors Info & Claims POPL '75: Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1975 Pages 1–9https://doi.org/10.1145/512976.512977Online:01 January 1975Publication History 13citation241DownloadsMetricsTotal Citations13Total Downloads241Last 12 Months8Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF