Reverse Strength Reduction
Strength reduction is a compiler optimisation that tries to replace expensive operations involving a loop variant with less expensive operations. The most common example of strength reduction is the replacement of array indexing with pointer arithmetic. Consider this program fragment:
where arr is an array of integers. An unoptimised compilation, in an RTL form, might look like this:
which would actually be some very nice RTL for the decompiler to discover because it is easy to recognise that arr is an array with stride 4 and replace statement 3 with:
unfortunately, the compiler will have gotten to the RTL before we have, and most any compiler will do some strength reduction to get rid of that multiply in the middle of the left of statement 3. So what the decompiler will see is more like this:
what we need to do is some analysis that will reverse the strength reduction and turn this RTL into that preferable RTL. As it turns out this isn't too hard to do for simple loops. Here's what the RTL looks like once it is in SSA form.
We can simply do a pass over the statements of the procedure looking for any assignment of the form x := x{p} + c where c is a constant and p is a PhiAssign that has only two elements, the assignment we're looking at and another assignment of the form x := 0. This a "high level pattern" and when matched it indicates that we can apply a "transformation". All we have to do to transform this RTL into the array indexing form is replace every occurance of r25{81}, except for the one in the increment statement, with r25{81} * c, and replace c in the increment statement with 1. Another high level pattern will recognise m[a[arr] + r25{81} * 4]and replace it with arr[r25{81}].
for (int i = 0; i < 25; i++)
arr[i] = 9;
where arr is an array of integers. An unoptimised compilation, in an RTL form, might look like this:
1 *32* r25 := 0
2 BRANCH 6
Highlevel: r25 >= 25
3 *32* m[a[arr] + r25 * 4] := 9
4 *32* r25 := r25 + 1
5 GOTO 2
which would actually be some very nice RTL for the decompiler to discover because it is easy to recognise that arr is an array with stride 4 and replace statement 3 with:
3 *32* a[r24] := 9
unfortunately, the compiler will have gotten to the RTL before we have, and most any compiler will do some strength reduction to get rid of that multiply in the middle of the left of statement 3. So what the decompiler will see is more like this:
1 *32* r25 := 0
2 BRANCH 6
Highlevel: r25 >= 100
3 *32* m[a[arr] + r25] := 9
4 *32* r25 := r25 + 4
5 GOTO 2
what we need to do is some analysis that will reverse the strength reduction and turn this RTL into that preferable RTL. As it turns out this isn't too hard to do for simple loops. Here's what the RTL looks like once it is in SSA form.
1 *32* r25 := 0
81 *32* r25 := phi(1, 4)
2 BRANCH 6
Highlevel: r25{81} >= 100
3 *32* m[a[arr] + r25{81}] := 9
4 *32* r25 := r25{81} + 4
5 GOTO 81
We can simply do a pass over the statements of the procedure looking for any assignment of the form x := x{p} + c where c is a constant and p is a PhiAssign that has only two elements, the assignment we're looking at and another assignment of the form x := 0. This a "high level pattern" and when matched it indicates that we can apply a "transformation". All we have to do to transform this RTL into the array indexing form is replace every occurance of r25{81}, except for the one in the increment statement, with r25{81} * c, and replace c in the increment statement with 1. Another high level pattern will recognise m[a[arr] + r25{81} * 4]and replace it with arr[r25{81}].
Comments
Post a Comment