Strength reduction example Strength reduction

1 strength reduction example

1.1 intermediate code
1.2 many optimizations
1.3 outer loop
1.4 last multiply

strength reduction example

below example strength-reduce loop multiplications arose array indexing address calculations.

imagine simple loop sets array identity matrix.

intermediate code

the compiler view code as

this expresses 2-dimensional array 1-dimensional array of n*n size, whenever high-level code expresses a[x, y] internally a[(x*n)+y] given valid indices x , y.

many optimizations

the compiler start doing many optimizations – not strength reduction. expressions constant (invariant) within loop hoisted out of loop. constants can loaded outside of both loops—such floating point registers fr3 , fr4. recognition variables don t change allow registers merged; n constant, r2, r4, r7, r12 can hoisted , collapsed. common value i*n computed in (the hoisted) r8 , r13, collapse. innermost loop (0120-0260) has been reduced 11 7 intermediate instructions. multiply remains in innermost loop line 0210 s multiply 8.

there more optimizations go. register r3 main variable in innermost loop (0140-0260); gets incremented 1 each time through loop. register r8 (which invariant in innermost loop) added r3. instead of using r3, compiler can eliminate r3 , use r9. loop, instead of being controlled r3 = 0 n-1, can controlled r9=r8+0 r8+n-1. adds 4 instructions , kills 4 instructions, there s 1 fewer instruction inside loop.

now r9 loop variable, interacts multiply 8. here strength reduction. multiply 8 can reduced successive additions of 8. there no multiplications inside loop.

registers r9 , r10 (= 8*r9) aren t both needed; r9 can eliminated in loop. loop 5 instructions.

outer loop

back whole picture:

there 4 multiplications within outer loop increments r1. register r8 = r1*r2 @ 0190 can strength reduced setting before entering loop (0055) , incrementing r2 @ bottom of loop (0385).

the value r8*8 (at 0118) can strength reduced initializing (0056) , adding 8*r2 when r8 gets incremented (0386).

register r20 being incremented invariant/constant r2 each time through loop @ 0117. after being incremented, multiplied 8 create r22 @ 0119. multiplication can strength reduced adding 8*r2 each time through loop.

the last multiply

that leaves 2 loops 1 multiplication operation (at 0330) within outer loop , no multiplications within inner loop.

at line 0320, r14 sum of r8 , r1, , r8 , r1 being incremented in loop. register r8 being bumped r2 (=n) , r1 being bumped 1. consequently, r14 being bumped n+1 each time through loop. last loop multiply @ 0330 can strength reduced adding (r2+1)*8 each time through loop.

there s still more go. constant folding recognize r1=0 in preamble, several instructions clean up. register r8 isn t used in loop, can disappear.

furthermore, r1 being used control loop, r1 can replaced different induction variable such r40. went 0 <= < n, register r40 goes 0 <= r40 < 8 * n * n.