Loop-invariant Optimization in the Pifagor Language

The paper considers methods of program transformation equivalent to optimizing the cycle invariant, applied to the functional data-flow model implemented in the Pifagor programming language. Optimization of the cycle invariant in imperative programming languages is reduced to a displacement from the cycle of computations that do not depend on variables that are changes in the loop. A feature of the functional data flow parallel programming language Pifagor is the absence of explicitly specified cyclic computations (the loop operator). However, recurring calculations in this language can be specified recursively or by applying specific language constructs (parallel lists). Both mechanisms provide the possibility of parallel execution. In the case of optimizing a recursive function, repeated calculations are carried out into an auxiliary function, the main function performing only the calculation of the invariant. When optimizing the invariant in computations over parallel lists, the calculation of the invariant moves from the function that executes over the list items to the function containing the call. The paper provides a definition of ”invariant” applied to the Pifagor language, algorithms for its optimization, and examples of program source codes, their graph representations (the program dependence graph) before and after optimization. The algorithm shown for computations over parallel lists is applicable only to the Pifagor language, because it rests upon specific data structures and the computational model of this language. However, the algorithm for transforming recursive functions may be applied to other programming languages.

1. In English: Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd Edition, Addison Wesley, 2006, 1000 pp.

2. Dortman P. A., “Program optimizacion in SFP”, Software tools and mathematical foundations of informatics, Novosibirsk, 2004, 43–49, (in Russian).

3. Legalov A. I., Matkovsky I. V., Kropacheva M. S., Udalova Y. V., Vasiliev V. M., “Tekhnologicheskie aspekty sozdaniya, preobrazovaniya i vypolneniya funkcionalno-potokovyh parallelnyh programm”, Nauchnyy servis v seti Internet: vse grani parallelizma: Trudy Mezhdunarodnoy superkompyuternoy konferentsii, Izd-vo MGU, M., 2013, 443–447, (in Russian).

4. Legalov A. I., Vasilyev V. S., Matkovskii I. V., Ushakova M. S., “Support tools for creation and transformation of functional-dataflow parallel programs”, Proceedings of ISP RAS, 29:5 (2017), 165–184, (in Russian).

5. Legalov A. I., “Functional language for creating of architectural independent parallel programs”, Computational Technologies, 10:1 (2005), 71–89, (in Russian).