CORNELL CS 612 - Scalar Optimization (59 pages)

Previewing pages 1, 2, 3, 4, 27, 28, 29, 30, 56, 57, 58, 59 of 59 page document View the full content.
View Full Document

Scalar Optimization



Previewing pages 1, 2, 3, 4, 27, 28, 29, 30, 56, 57, 58, 59 of actual document.

View the full content.
View Full Document
View Full Document

Scalar Optimization

122 views


Pages:
59
School:
Cornell University
Course:
Cs 612 - Compiler Design for High-Performance Architectures
Unformatted text preview:

Scalar Optimization 1 Organization 1 What kind of optimizations are useful 2 Program analysis for determining opportunities for optimization data ow analysis lattice algebra solving equations on lattices applications to data ow analysis 3 Speeding up data ow analysis exploitation of structure sparse representations control dependence SSA form sparse data ow evaluator graphs 2 Optimizations performed by most compilers Constant propagation replace constant valued variables with constants Common sub expression elimination avoid re computing value if value has been computed earlier in program Loop invariant removal move computations into less frequently executed portions of program Strength reduction replace expensive operations like multiplication with simpler operations like addition Dead code removal eliminate unreachable code and code that is irrelevant to output of program 3 Optimization example DO J 1 100 DO I 1 100 A I J 1 If we assume column major order of storage and 4 bytes per array element Address of A I J BaseAddress A J 1 100 4 I 1 4 BaseAddress A J 400 I 4 404 Only the term I 4 depends on I rest of computation is invariant in the inner loop and can be hoisted out of it Further hoisting of invariant code is possible since only the subterm J 400 depends on J Since I and J are incremented by 1 each time through the loop expressions like I 4 and J 400 can be strength reduced by replacing them with additions 4 Pseudo code for original loop nest DO J 1 100 DO I 1 100 t BaseAddress A J 400 I 4 404 STORE t 1 Pseudo code for optimized loop nest t0 BaseAddress A 404 DO J 1 100 t0 t0 400 t1 t0 DO I 1 100 t1 t1 4 STORE t 1 5 Terminology A de nition of a variable is a statement that may assign to that variable De nitions of x i x 3 ii F x y call by reference In second example invocation of F may write to x so to be safe we declare invocation to be a definition of x A use of a variable is a statement that may read the value of that variable Uses of x i y x 3 ii F x z 6 Aliasing occurs in a program when two or more names refer to the same storage location Examples i procedure f vax x y f z z f a b Within f reference parameters x and y may be aliases ii x 3 y x y 5 x x and y are aliases for the same location 7 Our position We will not perform analysis for variables that may be aliased such reference parameters local variables whose addresses have been taken etc This implies we can determine syntactically where all de nitions and uses of a variable are More re ned approach perform alias analysis 8 For the next few slides we will focus on constant propagation to illustrate the general approach to data ow analysis Examples i x 1 y x 2 if x z then y 5 fi y x 1 y 3 if 1 z then y 5 fi y Constant propagation may simplify control flow as well ii x 1 x 1 y x 2 y 3 dead code if y x then y 5 fi if true then y 5 simplify y 5 9 Why do opportunities for constant propagation arise in programs constant declarations for modularity macros procedure inlining small methods in OO languages machine speci c values 10 Overview of algorithm 1 Build the control ow graph of program makes ow of control in program explicit 2 Perform symbolic evaluation to determine constants 3 Replace constant valued variable uses by their values and simplify expressions and control ow 11 Step1 build the control ow graph CFG Example x 1 y x 2 if y x then y 5 fi y 12 START x 1 1 y x 2 1 3 y x 1 3 y 5 1 5 merge 1 5 y control flow graph CFG state vectorson CFG edges 13 Algorithm for building CFG easy only complication being break s and GOTO s need to identify jump targets Basic Block straight line code without any branches or merging of control ow Nodes of CFG statements or basic blocks switches merges Edges of CFG represent possible control ow sequence 14 Symbolic evaluation of CFG for constant propagation Propagate values from following lattice definitely not a constant false true 1 0 1 join T 0 T join 0 1 T meet 0 1 meet T 1 1 may or may not be constant Two operators join a b lowest value above both a and b also written as a b meet a b highest value below both a and b also written as a b Symbolic interpretation of expressions EVAL e Vin if any argument of e is or in Vin return or respectively otherwise evaluate e normally and return that value 15 1 Associate one state vector with each edge of the CFG initializing all entries to Initialize work list to empty 2 Set each entry of state vector on edge out of START to and place this edge on the worklist 16 3 while worklist is not empty do Get edge from worklist Let state vector on edge be Vin Symbolically evaluate target node of the edge using the state vectors on its inputs and propagate result state vector to output edge of node if target node is assignment statement x e Propagate Vin EVAL e Vin x to output edge else if target node is switch p if EVAL p Vin is T Propagate Vin to all outputs of switch else if EVAL p Vin is true Propagate Vin to true side of switch else Propagate Vin to false side of switch else target node is merge Propagate join of state vectors on all inputs to output If this changes the output state vector enqueue output edge on worklist od 17 Running example START x 1 1 y x 2 1 3 y x 1 3 y 5 1 5 merge 1 5 y control flow graph CFG state vectorson CFG edges 18 Algorithm can quite subtle START x 1 merge p x x x 1 First time through loop use of x in loop is determined to be constant 1 Next time through loop it reaches nal value 19 Complexity of algorithm Height of lattice 2 each state vector can change value 2 V times So while loop in algorithm is executed at most 2 E V times Cost of each iteration O V So overall algorithm takes O EV 2 time 20 Questions Can we use same work list based algorithm with di erent lattices to solve other analysis problems Can we improve the e ciency the algorithm Need to separate what is being computed from how it is being computed use algebras once again 21 Lattice algebraic approach to data ow analysis Abstractly our work list algorithm can be viewed as one solution procedure for solving a set of lattice algebraic equations Data ow lattices partially order set of nite height …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Scalar Optimization 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 Scalar Optimization 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?