Generation of optimal code for expressions via factorization

ABSTRACT

Given a set of expressions which are to be compiled, methods are presented for increasing the efficiency of the object code produced by first factoring the expressions, i.e. finding a set of subexpressions each of which occurs in two or more other expressions or subexpressions. Once all the factors have been ascertained, a sequencing procedure is applied which orders the factors and expressions such that all information is computed in the correct sequence and factors need be retained in memory a minimal amount of time. An assignment algorithm is then executed in order to minimize the total number of temporary storage cells required to hold the results of evaluating the factors. In order to make these techniques computationally feasible, heuristic procedures are applied, and hence global optimal results are not necessarily generated. The factorization algorithms are also applicable to the problem of factoring Boolean switching expressions and of factoring polynomials encountered in symbol manipulating systems.

REFERENCES

• 1: SMITH, J. Private communication.
• 2: Ward Douglas Maurer, Programming: An Introduction to Computer Techniques, Holden-Day, Incorporated, 1972
• 3: DIETMEYER, D. L., AND SCHNEIDER, P. R. A computeroriented factoring algorithm for NOR logic design. IEEE Trans. EC-14 (1965), 868-875.
• 4: DIETMEYER, D. L., AND Su, Y. H. Logic design automation of Fan in limited NAND networks. IEEE Trans. EC-18 (1969), pp. 11-22.
• 5: MILLER, R. E. Switching Theory, Vol. 1. Wiley, New York, 1966, pp. 220-229.
• 6: FR~BERO, E. Introduction to ALGOL Programming. Oxford U. Press, New York, 1964, p. 87.
• 7: Jesse H. Katz, Optimizing bit-time computer simulation, Communications of the ACM, v.6 n.11, p.679-685, Nov. 1963 [doi>10.1145/368310.368393]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms

Keywords:
code optimization, detection of common subexpressions, factorization algorithms, factorization of Boolean expressions, sequencing of operations