COMPILER OPTIMISATION I
IR Optimisations
Introduction
Copyright By PowCoder代写 加微信 powcoder
• We will consider a set of optimisations which a typical optimising compiler might perform.
• We will illustrate many transformations at the source level.
• important to remember that compiler usually parses code into an internal Intermediate Representation (IR) first and is making transformations at IR level
Programmer’s perspective:
These are (largely) optimisations which you would expect a compiler to do, and should very rarely be hand-coded.
• IR level optimisations
• Basic optimisations
• Redundancy elimination
• Loop optimisations
• Procedure call optimisations
Basic optimisations
Begin by looking at some simple optimisations: • Constant folding
• Algebraic simplifications
• Copy propagation
• Constant propagation
• Fairly complex transformations can be achieved by combining simple ones.
• Requires multiple optimisation passes
Constant folding
• Where possible, replace variables with constants at compile time.
• Reduces memory references (value stored in instruction, rather than in data).
• Expressions that only involve constants can be evaluated at compile time
• Take care with expressions which might result in errors (overflow, divide by zero).
• For floating point, must ensure that compiler will generate same results as executed code.
integer, parameter :: n=100
do i=1,n ….
do j=1,n/2 ….
do i=1,100 ….
do j=1,50 ….
Algebraic simplifications
• Compiler can recognise and simplify algebraic expressions.
• Very simple examples: i+0 i
i + (-j) i-j i**2 i*i
• Can also make use of associativity and commutativity: (i-j)+(i-j)+(i-j) 3*i – 3*j
Algebraic simplifications
• Many more restrictions apply to floating point than to integers
• floating point operations are not associative Suppose MF is largest representable floating point
value 1.0 + (MF – MF) = 1.0 (1.0 + MF) – MF = 0.0
Copy propagation
• Given an assignment (x=y), we can replace later uses of x with y, provided no changes to either x or y have occurred in the meantime.
• Can reduce memory references, or number of registers required
c =x+ 3 c = y+ 3 d =x+ y d = y+ y
Constant propagation
• If a variable x is assigned a constant value, then subsequent references to x can be replaced by the constant, provided no changes to x occur in the meantime.
• Reduces number of registers required
• Aids later transformations, such as constant
expression evaluation.
c =x+ 3 c =4+ 3 d =x+ y d =4+ y
Redundancy elimination
The next set of transformations deal with removing redundant computations.
• Common subexpression elimination (CSE)
• Loop invariant code motion
• Algebraic simplification in redundancy elimination • Dead code elimination
• If a part of an expression occurs twice, and the variables involved are not changed between the two evaluations, then the computation can be done once and the result stored in a temporary.
• May not always be beneficial
• increases number of registers required
a = b + (c – 2) d = 4 *b
e = d + (c – 2)
t1 = c – 2 a = b + t1 d = 4 *b e = d + t1
Loop invariant code motion
• Expressions which occur inside a loop, but give the same result on all loop iterations, can be computed once, outside the loop.
• Can be applied to more than one level of loop
do i = 1,n do j = 1,n
a(j,i)=2*b(i+1)+j-(m*5)
do i = 1,n
t2 = 2*b(i+1) do j = 1,n
a(j,i)=t2 + j – t1
Algebraic simplification again
• Use of algebraic simplification can help in redundancy elimination
do i=1,n a=b+i c=a-i d=b+i
do i=1,n a=b+i c=a-i
d=a end do
do i=1,n a=b+i
loop invariance
Dead code elimination
• Removes code whose results are never used.
• May be used several times in optimisation process,
as other optimisations may create dead code. • Something to beware of in small benchmarks!
d = a+b; printf(“%d\n”, d);
d = a+b; printf(“%d\n”, d);
Simple loop optimisations
This set of optimisations apply to loops
N.B. Need “well-structured” loops, (Fortran DO loop) – to apply to C or Java, need to identify a class of suitable for loops.
• Strength reduction
• Induction variable removal
• Bounds checking elimination
Induction variables
• An induction variable is a variable in a loop whose value on successive iterations forms an arithmetic progression.
• Example:
a(j) = b(i)
Strength reduction
• Replaces explicit computation based on loop iterator with increments
• Reduces number of operations required at the
expense of more registers.
for (i=0;i