Cleaning up the CFG Eliminating useless nodes & edges COMP 512 Rice University Houston, Texas Spring 2009 Copyright 2009, Keith D. Cooper & Linda Torczon, all rights reserved. Students enrolled in Comp 512 at Rice University have explicit permission to make copies of these materials for their personal use. The primary algorithm described in this lecture is due to Rob Shillner, when he worked on the MSCP at Rice. To our knowledge, the only published version of the algorithm is in Chapter 10 of EaC. 1!COMP 512, Spring 2009!COMP 512, Spring 2009! 2!Dead Code Elimination Three distinct problems •! Useless operations >! Any operation whose value is not used in some visible way >! Use the SSA-based mark/sweep algorithm (DEAD) •! Useless control flow >! Branches to branches, empty blocks >! Simple CFG-based algorithm (Shillner’s CLEAN) •! Unreachable blocks >! No path from n0 to b ! b cannot execute >! Simple graph reachability problemCOMP 512, Spring 2009! 3!Eliminating Useless Control Flow The Problem •! After optimization, the CFG can contain empty blocks •! “Empty” blocks still end with either a branch or a jump •! Produces jump to jump, which wastes time & space •! Need to simplify the CFG & eliminate these The Algorithm (CLEAN) •! Use four distinct transformations •! Apply them in a carefully selected order •! Iterate until done Devised by Rob Shillner (1992), documented by John Lu (1994) We must distinguish between these •! Branch is conditional •! Jump is absolute COMP 512, Spring 2009! 4!Eliminating Useless Control Flow Transformations B1 B2 B1 B2 Eliminating redundant branches Both sides of branch target Bi •! Neither block must be empty •! Replace it with a jump to Bi •! Simple rewrite of last op in B1 How does this happen? •! Rewriting other branches How do we find it? •! Check each branch Branch, not a jump *COMP 512, Spring 2009! 5!Eliminating Useless Control Flow Transformations Merging an empty block •! Empty B1 ends in a jump •! Coalesce B1 with B2 •! Move B1’s incoming edges •! Eliminates extraneous jump •! Faster, smaller code How does this happen? •! Eliminate operations in B1 How do we find it? •! Test for empty block Eliminating empty blocks B2 B1 B2 empty COMP 512, Spring 2009! 6!Eliminating Useless Control Flow Transformations Coalescing blocks •! Neither block must be empty •! B1 ends with a jump •! B2 has 1 predecessor •! Combine the two blocks •! Eliminates a jump How does this happen? •! Simplifying edges out of B1 How do we find it? •! Check target of jump |preds | Combining non-empty blocks B1 B2 B1 B2 B1 and B2 should be a single basic block If one executes, both execute, in linear order. *COMP 512, Spring 2009! 7!Eliminating Useless Control Flow Transformations Jump to a branch •! B1 ends with jump, B2 is empty •! Eliminates pointless jump •! Copy branch into end of B1 •! Might make B2 unreachable How does this happen? •! Eliminating operations in B2 How do we find this? •! Jump to empty block Hoisting branches from empty blocks B1 B2 empty B1 B2 empty COMP 512, Spring 2009! 8!Eliminating Useless Control Flow Putting the transformations together •! Process the blocks in postorder >! Clean up Bi’s successors before Bi >! Simplifies implementation & understanding •! At each node, apply transformations in a fixed order >! Eliminate redundant branch >! Eliminate empty block >! Merge block with successor >! Hoist branch from empty successor •! May need to iterate >! Postorder ! unprocessed successors along back edges >! Can bound iterations, but a deriving tight bound is hard >! Must recompute postorder between iterations Creates a jump that should be checked in the same pass { Handle jump * "! Eliminates an edge "! Eliminates a node "! Eliminates node & edge "! Adds an edgeCOMP 512, Spring 2009! 9!Eliminating Useless Control Flow What about an empty loop? •! By itself, CLEAN cannot eliminate the loop •! Loop body branches to itself >! Branch is not redundant >! Doesn’t end with a jump >! Hoisting does not help •! Key is to eliminate self-loop >! Add a new transformation? >! Then, B1 merges with B2 B0 B2 B1 * Targets two distinct blocks! B0 B2 B1 * B0 B2 B1 * New transformation must recognize that B1 is empty. Presumably, it has code to test exit condition & (probably) increment an induction variable. This requires looking at code inside B1 and doing some sophisticated pattern matching. This seems awfully complicated. * COMP 512, Spring 2009! 10!Eliminating Useless Control Flow What about an empty loop? •! How to eliminate <B1,B1> ? >! Pattern matching ? >! Useless code elimination ? B0 B2 B1 *COMP 512, Spring 2009! 11!Eliminating Useless Control Flow What about an empty loop? •! How to eliminate <B1,B1> ? >! Pattern matching ? >! Useless code elimination ? •! What does DEAD do to B1? >! Remember, it is empty >! Contains only the branch >! B1 has only one exit >! So, B1 # RDF(B2) >! B1’s branch is useless >! DEAD rewrites it as a jump to B2 B0 B2 B1 * COMP 512, Spring 2009! 12!Using SSA – Dead code elimination Mark for each op i clear i’s mark if i is critical then mark i add i to WorkList while (Worklist ! Ø) remove i from WorkList (i has form “x!y op z” ) if def(y) is not marked then mark def(y) add def(y) to WorkList if def(z) is not marked then mark def(z) add def(z) to WorkList for each b $ RDF(block(i)) mark the block-ending branch in b add it to WorkList Sweep for each op i if i is not marked then if i is a branch then rewrite with a jump to i’s nearest useful post-dominator if i is not a jump then delete i Notes: •! Eliminates some branches •! Reconnects dead branches to the remaining live code •! Find useful post-dominator by walking post-dom tree >! Entry & exit nodes are useful Shillner added this clauseCOMP 512, Spring 2009! 13!Eliminating Useless Control Flow What about an empty loop? •! How to eliminate <B1,B1> ? >! Pattern matching ? >! Useless code elimination ? •! What does DEAD do to B1? >! Remember, it is empty >! Contains only the branch >! B1 has only one exit >! So, B1 # RDF(B2) >! B1’s branch is useless >! DEAD rewrites it as a jump to B2 DEAD converts it to a form where CLEAN handles it ! B0 B2 B1 B0 B2 B1 DEAD COMP 512, Spring 2009! 14!Eliminating Useless