Reasoning About Program Transformations : Imperative Programming and Flow of Data

Overview The motivation of this text lies in what we believe is the inadequacy of current frameworks to reason about the ?ow of data in imperative programs. This inadequacy clearly shows up when dealing with the individual side effects of loop iterations. - deed, we face a paradoxical situation where, on the one hand, a typical program spends most of its execution time iterating or recursing on a few lines of codes, and, on the other hand, current optimization frameworks are clumsy when trying to capture the effects of each incarnation of these few lines—frameworks we inherited from designs made decades ago. The reasons are manyfold, but one of them stands out: The same concepts have been used, on the one hand, to represent and manipulate programs internally in compilers and, on the other hand, to allow us humans to reason about optimizations. Unfortunately, these two uses have different aims and constraints. An example of such a situation is given by control-?ow graphs of basic blocks, which have been - tremely useful in practice as an internal representation of programs, but which are not always adequate or convenient to formally think about programs and specify their transformations. In some cases, de?nitions based on control-?ow graphs can be overly restrictive. Dominance, studied in Chapter 4, is a good example.

the Book Focuses On Analyses That Extract The Flow Of Data, Which Imperative Programming Hides Through Its Use And Reuse Of Memory In Computer Systems And Compilers. It Details Some Program Transformations That Conserve This Data Flow And Introduces A Family Of Analyses, Called Reaching Definition Analyses, To Do This Task. In Addition, It Shows That Correctness Of Program Transformations Is Guaranteed By The Conservation Of Data Flow. Professionals And Researchers In Software Engineering, Computer Engineering, Program Design Analysis, And Compiler Design Will Benefit From Its Presentation Of Data-flow Methods And Memory Optimization Of Compilers.

Front Matter....Pages I-XVIII Introduction....Pages 1-15 Front Matter....Pages 17-17 Describing Program Executions....Pages 19-35 Labels....Pages 37-55 Front Matter....Pages 57-57 Revisiting Some Classical Compiler Concepts....Pages 59-76 Reaching Definition Analysis....Pages 77-122 Applications of Reaching Definition Analysis....Pages 123-142 Some Classical Compiler Concepts, Part II....Pages 143-162 Front Matter....Pages 163-163 Single-Assignment Forms....Pages 165-194 Maximal Static Expansion....Pages 195-210 Parallel Languages....Pages 211-222 Conclusion: Toward Algorithm Recognition....Pages 223-227 Back Matter....Pages 229-237 The text contains a detailed and current presentation of the program analyses and transformations that extract the flow of data in computer memory systems. The emphasis is on a framework for the optimization of code for imperative programs and greater computer systems efficiency. In addition, the author shows that correctness of program transformations is guaranteed by the conservation of data flow. Professionals and researchers in software engineering, computer engineering, program design analysis, and compiler design will benefit from its presentation of data-flow methods and memory optimization of compilers. "This new book provides a detailed, current, and pragmatic presentation of the program analyses and transformations that extract the flow of data in computer memory systems. Professionals, practitioners, and researchers in software engineering, computer engineering, program design analysis, and compiler design will benefit from its presentation of data-flow and memory optimization techniques and tools."--BOOK JACKET. Algorithms were invented thousands of years ago, when the only thinkable machine to do computations were human beings' own gray cells.