Lazy Code Motion and Partial Redundancy Elimination in Optimizing Compiler
Lazy code motion, partial redundancy elimination, common subexpression elimination, and loop invariant code motion are optimization techniques used in compilers to improve code efficiency by eliminating redundant computations and moving code blocks to optimize performance. These techniques aim to delay computations, reduce redundancy, and improve register allocation for efficient execution of programs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lazy Code Motion Bojian Zheng CSCD70 Spring 2018 bojian@cs.toronto.edu 1
Partial Redundancy Elimination Can we replace calculations of ? + ? such that no path re-executes the same expression? subsumes Global Common Subexpression Full Redundancy Loop Invariant Code Motion Partial Redundancy for-loops 2
Common Subexpression Elimination On every path reaching ? Expression ? + ? has been computed. Neither ? nor ? is overwritten after the expression. 3
Loop Invariant Code Motion Given an expression ? + ? inside a loop, Does the value of ? + ? change inside the loop? Is the code executed at least once? 4
Lazy Code Motion The optimization of eliminating partial redundancy with the goal of delaying the computations as much as possible. How are we going to achieve this? Anticipated Expressions & Will-be-Available Expressions Postponable Expressions Used Expressions 6
Our Goal Safety Maximum Redundancy Elimination Shortest Register Lifetime 7
Safety We cannot introduce operations that are not executed originally. Given the diagram on the right, can we insert the expression ? + ? on the right parent? 9
Anticipated Expressions An expression ? is said to be anticipated at program point ? if all paths leading from ? eventually computes ? (from the values of ? s operands that are available at ?). 10
Safety We cannot introduce operations that are not executed originally. Given the diagram on the right, can we insert the expression ? + ? on the right parent? NO! The reason is because ? + ? is not anticipated at the right parent. 11
Critical Edge If the source has multiple successors, and the destination has multiple predecessors, then the path that is connecting them is defined as Critical Edge. 12
Solution: Synthetic Block Add a basic block for every edge that leads to a basic block with multiple predecessors (not just the back edge). This simplifies the algorithm since we can always place at the beginning of the basic block. 13
Example 1 What is the result after insertion at the anticipation frontier? 14
Example 2: Loop Invariance Will insertion at the anticipation frontier help in this case? 15
Example 3: More Complex Loop Where are we expecting to place expression ? + ?? Where will it actually be placed? 16
Example 4: Complex Loop Variation Can we place expression ? + ? at the left synthetic block like what we did previously? 17
Questions? Keywords: Safety Anticipated Expressions Synthetic Block 18
Complications Does the anticipation frontier approach always work? The reason is because we have not yet considered expression availability. Want to make the expression ? available wherever it is anticipated but unavailable. 20
Will-be-Available Expressions An expression ? is said to be will-be-available at program point ? if it is anticipated and not subsequently killed along all paths reaching ?. Note how it is different from Available Expressions. 21
Early Placement earliest ? is the set of expressions added to block ? under early placement, and is computed from the results of anticipated and will-be-available. earliest ? = anticipated.in ? in will be available ? in 22
Example Where is the earliest placement? Is it different from the anticipation frontier? 23
Questions? Keywords: Will-be-Available Expressions Early Placement 24
Shortest Register Lifetime? Early Placement goes against our goal of shortest register lifetime. We want to delay creating redundancy to reduce register pressure. 26
Postponable Expressions An expression ? is said to be postponable at program point ? if all paths leading to ? have seen earliest placement of ? but not a subsequent use. 27
Example 28
Latest Placement We define the term Latest as follows: It is ok to place the expression ?: either Earliest or Postponable . Need to place at ? if either: ? is used in ? . It is NOT ok to place in one of its successors . Latest ? = earliest ? postponable ? EUse ? postponable ? ? succ ? 29
Example 30
Questions? Keywords: Postponable Expressions Latest Placement 31
Used Expressions An expression ? is said to be used at program point ? if there exists a path leading from ? that uses the expression before the operands are reevaluated. 33
Final Placement Our code transformation goes as follows: ?, if expression ? latest ? used ? at the beginning of ?, insert ? = ?, and replace every original ? with ? 34
Summary 35
