E-path_PRE - Partial redundancy elimination made. easy
| Autor: | Dhananjay M. Dhamdhere |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2002 |
| Předmět: |
Loop invariant
Correctness Computer science Strength Reduction Transformation Partial redundancy elimination computer.software_genre Redundancy (information theory) Data-Flow-Analysis Partial Redundancy Elimination Redundancy (engineering) Common subexpression elimination Code Motion Redundant code Data-flow analysis Code Optimization Program optimization Computer Graphics and Computer-Aided Design Eliminatability Of Expressions Algorithm Edge Placement Reality Data Flow Analysis Redundant Code Movement Compiler Global Program Optimization computer Software |
| Zdroj: | IndraStra Global. |
| ISSN: | 2381-3652 |
| Popis: | Partial redundancy elimination (PRE) subsumes the classical optimizations of loop invariant movement and common subexpression elimination. The original formulation of PRE involved complex bi-directional data flows and had two major deficiencies---missed optimization opportunities and redundant code movement. To eliminate redundant code movement, most current PRE approaches use a hoisting-followed-by-sinking approach. Unfortunately, this approach has a high conceptual complexity and requires complicated correctness proofs.We show that optimization by partial redundancy elimination is simpler than it has been made out to be. Its essence is the concept of eliminatability of an expression. We show that E-path_PRE, a formulation of PRE based on the concept of eliminatability paths (E-paths), is easy to understand and simple to prove correct. It uses only well-known data flow concepts of available expressions and anticipatable (i.e. very-busy) expressions to directly identify code insertion points which avoid redundant code movement. These features reduce the conceptual complexity of PRE considerably. Interestingly, performance studies show that E-path_PRE is also less expensive to perform than the closest equivalent approach to PRE. This is a sheer bonus. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|