UMass Amherst CMPSCI 710 - Partial Redundancy Elimination (21 pages)

Previewing pages 1, 2, 20, 21 of 21 page document View the full content.
View Full Document

Partial Redundancy Elimination



Previewing pages 1, 2, 20, 21 of actual document.

View the full content.
View Full Document
View Full Document

Partial Redundancy Elimination

32 views

Lecture Notes


Pages:
21
School:
University of Massachusetts Amherst
Course:
Cmpsci 710 - Advanced Compilers

Unformatted text preview:

Advanced Compilers CMPSCI 710 Spring 2003 Partial Redundancy Elimination Emery Berger University of Massachusetts Amherst UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science Topics Last time Common subexpression elimination Value numbering Global CSE This time Partial redundancy elimination UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 2 Partial Redundancy Partial redundancy Expression computed more than once on some path through control flow graph Partial redundancy elimination PRE Minimizes partial redundancies Inserts and deletes computations adds temps Each path contains no more usually fewer occurrences of any computation than before Dominates global CSE loop invariant code motion UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 3 PRE Example UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 4 PRE Problem Critical edge prevents redundancy elimination Connects node with two or more successors to one with two or more predecessors Why is it a problem UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 5 PRE Solution Split critical edges Insert empty basic blocks Allows PRE to continue UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 6 Big Example Critical Edges UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 7 Big Example Critical Edges Removed UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 8 PRE Dataflow Equations First formulation Morel Renvoise 79 bidirectional dataflow analysis Ugly This version Knoop et al 92 Based on lazy code motion Places computations as late as possible Same reductions as classic algorithm Minimizes register pressure Most complex dataflow problem we ve ever seen UNIVERSITY OF MASSACHUSETTS AMHERST Department of Computer Science 9 Step 1 Local Transparency Expression s value is locally transparent in a basic block if No assignments to variables that occur in expression Set of locally transparent



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Partial Redundancy Elimination and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Partial Redundancy Elimination and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?