UMass Amherst CMPSCI 710 - Basic Loop Optimizations (16 pages)

Previewing pages 1, 2, 3, 4, 5 of 16 page document View the full content.
View Full Document

Basic Loop Optimizations



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document
View Full Document

Basic Loop Optimizations

31 views


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

Unformatted text preview:

Advanced Compilers CMPSCI 710 Spring 2003 Basic Loop Optimizations Emery Berger University of Massachusetts Amherst UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE Topics Last time Optimizations using SSA form Constant propagation dead code elimination Loop invariant code motion This time Loop optimizations Induction variable Linear test replacement Loop unrolling Scalar replacement UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 2 Easy Detection of Loop Induction Variables Pattern match check Search for i i b in loop i is induction variable if no other assignment to i in loop Pros Cons Easy Does not catch all loop induction variables e g i a c 2 UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 3 Taxonomy of Induction Variables basic induction variable only definition in loop is assignment j j c where c is loop invariant mutual induction variable definition is linear function of other induction variable i i c1 i c2 i i c1 c2 family of basic induction variable j set of induction variables i such that i is always assigned linear function of j UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 4 Strength Reduction Replace expensive op by cheaper one E g replace multiply by addition Apply to induction variable families Especially array indexing UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 5 Strength Reduction Algorithm Let i be induction variable in the family of basic induction variable j i c1 j c2 Create new variable i Initialize in pre header i c1 j c2 Track value of j after j j c3 add i i c1 c3 UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 6 Strength Reduction Example UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 7 Candidates for Strength Reduction Induction variable IV multiplied by invariant Recursively IV IV IV mod constant IV IV UNIVERSITY OF MASSACHUSETTS AMHERST DEPARTMENT OF COMPUTER SCIENCE 8 Strength Reduction Algorithm



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Basic Loop Optimizations 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 Basic Loop Optimizations 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?