Original code: Thumb->ARM: Propagation: Elimination:
ldr r1, [pc, #37] ldr r1, [pc, #37] ldr r1, [pc, #37] ldr r1, [pc, #37]
add r0, r4, r1 adds r0, r4, r1 adds r0, r4, r1
ldrb r0, [r0, #0] ldrb r0, [r0] ldrb r0, [r4, r1] ldrb r0, [r4, r1]
mov r1, #3 movs r1, #3 movs r1, #3
and r1, r0 ands r1, r1, r0 ands r1, r0, #3 and r1, r0, #3
mov r2, #188 movs r2, #188 movs r2, #188
lsl r2, r2, #1 movs r2, r2, lsl #1 movs r2, #376
add r0, r4, r2 adds r0, r4, r2 adds r0, r4, #376
ldrh r5, [r0, #0] ldrh r5, [r0] ldrh r5, [r4, #376] ldrh r5, [r4, #376]
mov r0, r4 movs r0, r4 movs r0, r4
add r0, #76 adds r0, r0, #76 adds r0, r4, #76
ldrb r0, [r0, #0] ldrb r0, [r0] ldrb r0, [r4, #76] ldrb r0, [r4, #76]
mov r6, #7 movs r6, #7 movs r6, #7
and r6, r0 ands r6, r6, r0 ands r6, r0, #7 and r6, r0, #7
mov r3, #186 movs r3, #186 movs r3, #186
lsl r3, r3, #1 movs r3, r3, lsl #1 movs r3, #376
add r0, r4, r3 adds r0, r4, r3 adds r0, r4, #376
ldr r2, [r0, #0] ldr r2, [r0] ldr r2, [r4, #376] ldr r2, [r4, #376]
mov r0, r4 movs r0, r4 movs r0, r4
add r0, #154 adds r0, r0, #154 adds r0, r4, #154
ldrb r3, [r0, #0] ldrb r3, [r0] ldrb r3, [r4, #154] ldrb r3, [r4, #154]
mov r7, #15 movs r7, #15 movs r7, #15 mov r7, #15
mov r0, r7 movs r0, r7 movs r0, #15
and r0, r3 ands r0, r0, r3 ands r0, r3, #15 and r0, r3, #15
lsl r0, r0, #2 movs r0, r0, lsl #2 movs r0, r0, lsl #2 (')
add r1, r1, r0 adds r1, r1, r0 adds r1, r1, r0', lsl #2 add r1, r1, r0, lsl #2
lsl r0, r6, #2 movs r0, r6, lsl #2 movs r0, r6, lsl #2
add r0, r0, r6 adds r0, r0, r6 adds r0, r6, r6 lsl #2 add r0, r6, r6 lsl #2
lsl r0, r0, #2 movs r0, r0, lsl #2 movs r0, r0, lsl #2 (')
add r1, r1, r0 adds r1, r1, r0 adds r1, r1, r0', lsl #2 add r1, r1, r0, lsl #2
add r2, #128 adds r2, r2, #128 adds r2, r2, #128 add r2, r2, #128
add r2, r2, r1 adds r2, r2, r1 adds r2, r2, r1 (')
ldrb r0, [r2, #0] ldrb r0, [r2] ldrb r0, [r2', r1] ldrb r0, [r2, r1]
lsl r2, r0, #4 movs r2, r0, lsl #4 movs r2, r0, lsl #4 (') mov r2, r0, lsl #4
cmp r5, #16 cmp r5, #16 cmp r5, #16 cmp r5, #16
ble 803bdb2 ble l1 ble l1 ble l1
mov r5, #16 movs r5, #16 movs r5, #16 mov r5, #16
l1: l1: l1:
lsl r0, r5, #1 movs r0, r5, lsl #1 movs r0, r0', lsl #5 mov r0, r0, lsl #5
ldr r3, [pc, #19] ldr r3, [pc, #19] ldr r3, [pc, #19] ldr r3, [pc, #19]
add r1, r4, r3 adds r1, r4, r3 adds r1, r4, r3
ldrb r1, [r1, #0] ldrb r1, [r1] ldrb r1, [r4, r3] ldrb r1, [r4, r3]
add r1, r2, r1 adds r1, r2, r1 adds r1, r2, r1 add r1, r2, r1
add r1, r1, r0 adds r1, r1, r0 adds r1, r1, r0 add r1, r1, r0
mov r0, r4 movs r0, r4 movs r0, r4
add r0, #188 adds r0, r0, #188 adds r0, r4, #188
ldr r2, [r0, #0] ldr r2, [r0] ldr r2, [r4, #188] ldr r2, [r4, #188]
mov r0, r2 movs r0, r2 movs r0, r2 mov r0, r2
cmp r2, #0 cmp r2, #0 cmp r2, #0 cmp r2, #0
bge 803bdce bge l2 bge l2 bge l2
ldr r3, [pc, #15] ldr r3, [pc, #15] ldr r3, [pc, #15] ldr r3, [pc, #15]
add r0, r2, r3 adds r0, r2, r3 adds r2, r2, r3 add r2, r2, r3
l2: l2: l2:
asr r0, r0, #16 mov r0, r0, asr #16 mov r0, r0, asr #16 (')
sub r0, r1, r0 subs r0, r1, r0 subs r0, r1, r0', asr #1 sub r0, r1, r0, asr #16
cmp r0, #0 cmp r0, #0 cmp r0, #0 cmp r0, #0
blt 803be10 blt x1 blt x1 blt x1
asr r0, r2, #16 movs r0, r2, asr #16 movs r0, r2, asr #16 mov r0, r2, asr #16
ldr r1, [pc, #12] ldr r1, [pc, #12] ldr r1, [pc, #12] ldr r1, [pc, #12]
cmp r0, r1 cmp r0, r1 cmn r1, r2, asr #16 cmn r1, r2, asr #16
ble 803bde0 ble l3 ble l3 ble l3
mov r0, r1 movs r0, r1 movs r0, r1 mov r0, r1
l3: l3: l3:
asr r2, r0, #6 movs r2, r0, asr #6 movs r2, r0, asr #6
and r2, r7 ands r2, r2, r7 ands r2, r7, r0, asr #6 and r2, r7, r0, asr #6
mov r3, r4 movs r3, r4 movs r3, r4
add r3, #192 adds r3, r3, #192 adds r3, r4, #192 add r3, r4, #192
mov r1, #186 movs r1, #186 movs r1, #186
lsl r1, r1, #1 movs r1, r1, lsl #1 movs r1, #372
add r0, r4, r1 adds r0, r4, r1 adds r0, r4, #372
ldr r0, [r0, #0] ldr r0, [r0] ldr r0, [r4, #372] ldr r0, [r4, #372]
lsl r1, r6, #4 movs r1, r6, lsl #4 movs r1, r6, lsl #4 mov r1, r6, lsl #4
add r2, r2, r1 adds r2, r2, r1 adds r2, r2, r6, lsl #4 add r2, r2, r6, lsl #4
add r0, r0, r2 adds r0, r0, r2 adds r0, r0, r2 (') adds temp, r0, r2
ldrb r0, [r0, #0] ldrb r0, [r0] ldrb r0, [r0', r2] ldrb r0, [r0', r2]
lsl r0, r0, #12 movs r0, r0, lsl #12 movs r0, r0, lsl #12 (') movs r0, r0, lsl #12
str r0, [r3, #0] str r0, [r3] str r0, [r3] str r0, [r3]
b 803bf2e b x2 b x2 b x2
Input: 75 instructions
Output: 47 instructions
Stages:
Pass 1: Thumb to ARM conversion
In this step, Thumb instructions are converted to ARM instructions. This
doesn't change any of the functionality of the instrcutions, but mainly
expands them to three address forms to allow for more propagation in the
later passes. Shifts are also converted to moves with shifted arguments.
Additionally some changes were made for clarity: labels were added and
branch targets were changed to these. Load/store immediate offsets of
#0 were dropped - this will be important in allowing addressing
propagation.
Note that most Thumb ALU ops modify flags, which appears in the explicit
"s" at the end of the translated ARM opcode mneumonics.
Pass 2: propagation and aliasing
Here, register propagation. propagation means that whenever a register
changes, the next time that register is referenced the original
expression it was changed to will be substituted in instead, until the
register is modified again. This will be made clearer with the following
examples. Naturally, it only makes sense to propogate values to the point
where they may still be useful, so the following propagations are
performed:
Move propagation:
When register a is moved to register b, register a will be referenced
instead of register b later on.
movs r0, r1 < "r1" propogates to r0
adds r0, r0, r1 < r0 is substituted with "r1"
adds r0, r0, r0 < the first propagation is now dead
This becomes:
movs r0, r1
adds r0, r1, r1
adds r0, r0, r0
Constant propagation:
When constant #x is moved to register a, #x will be used instead of
register a where possible. A constant is possible in the second slot of
a standard arithmetic operation.
movs r0, #1
adds r0, r1, r0
Becomes:
movs r0, #1
adds r0, r1, #1
Shift propagation:
When a shift expression (a SHIFT b) is moved to register c, (a SHIFT b)
will be referenced instead of register c where possible. Like constants,
shift operations are possible in the second slot of a standard arithmetic
operation.
movs r0, r1, lsl #2
adds r0, r1, r0
Becomes:
movs r0, r1, lsl #2
adds r0, r1, r1, lsl #2
Addition/subtraction propagation:
When a subtraction (a +/ b) is moved to register c, (a +/- b)
will be referenced instead of register c if in a memory addressing location
[c].
adds r0, r1, r2
ldrs r0, [r0]
Becomes:
adds r0, r1, r2
ldrs r0, [r1, r2]
Add/sub + shift propagation:
Not done, but might be useful sometimes. Like the above, only an entire
(a +/ (b SHIFT c)) expression is propogated, something which can be handled
in native ARM.
General ALU propagation:
This isn't done, and probably isn't worthwhile, but might win some
occasionally. Basically, any operation can be propogated if a move
is done later. However, that move would probably be made dead anyway.
Commutative flipping:
Often propagation will occur in the first slot of an arithmetic operation,
instead of the second. Fortunately, most arthimetic operations are either
commutative or have a reverse version, and thus the operations can be
flipped.
movs r0, r1, lsl #2
subs r0, r0, r1
Becomes:
movs r0, r1, lsl #2
rsbs r0, r1, r1, lsl #2
Constant folding:
If an arithmetic operation ends up having two constants, then they will
be folded into a single move (in other words, the arithmetic operation
will be performed at runtime)
movs r0, #2
adds r0, r0, #2
Becomes:
movs r0, #2
movs r0, #4
Shift folding:
This is a bit more complex and probably not much of a win - it's done
once in the above, but it doesn't end up winning anything later. It may
not be of any real interest.
Register aliasing:
This technique is used for propagations more complex than simple move or
constant propagation (actually, it would apply to mov a, a where a is the
same register, but it is assumed that such a thing is never actually done
since it'd be a nop.. if it is that can be special cased out)
If the destination is the same as one of the sources, then the propagation
will be "dead" before it's even useful for the first time. To get around
this, a (') was added to the end of the expression, basically that means
that an additional move to a new register is made, in the hopes that no
such new register will ever actually be needed (in the next pass).
Basically, the (') indicates that the register which is being overwritten
will first be copied to a temporary register named a'. Then, whereever
a can be propogated, a' will be used in the expansion. Whereever it can't
be propogated, a will be used.
Since double propagation shouldn't be possible with these expressions
(maybe with some of the techniques not used) then a '' alias shouldn't
show up, at least limiting things somewhat.
movs r0, r0, lsl #1
adds r0, r1, r0
Becomes:
movs r0, r0, lsl #1 (')
adds r0, r1, r0', lsl #1
The line:
movs r0, r0, lsl #1 (')
Can be thought of as:
movs r0', r0
movs r0, r0', lsl #1
However, for the sake of the next pass, it's important that this remains an
atomic unit.
Register aliasing is the most complicated transformation that is actually
explained in detail here, and thus may not be done (or may be saved for
last). It also has the unfortunate requirement of needing extra information
stored with the instruction to determine if a register or its alias is
being used in the expression. A 4bit mask per instruction is sufficient to
determine this.
Pass 3: Dead target elimination and de-aliasing
Liveness analysis:
This is a pass must first be done for the actual work to be possible.
At any line it is determined if the destination register and/or modified
flags are "alive" at any point afterwards. What this means is that the register
or flags are used somewhere later on in the block before they is overwritten.
Of course, this only applies to lines that modify a destination register or flags,
but almost all have one.
For instance:
movs r0, r1 < r0 is dead here because it's overwritten
movs r0, #5 < here before it's ever used (and flags too)
On the other hand:
adds r0, r1, r2 < r0 is alive here because it's used
adds r3, r0, r4 < as a source here
And:
adds r0, r1, r2 < r0 is dead, but the c and v flags are live
movs r0, #5 < doesn't overwrite c, v
Dead target elimination:
Lines that have a destination which is dead can be eliminated altogether;
they are effectively nops. The work done in the previous pass will make
several lines dead.
movs r0, #5
adds r0, r1, #5
Becomes:
adds r0, r1, #5
Also, if the modified flags are dead at a given point, the "s" is dropped
from the instructions (however, "partial" liveness of flags is useful
information to keep around so that only some flags need to be evaluated).
Note that the instructions likely to not be eliminated are the ones near
the end of the block, where they may or may not be alive after the block.
With some kinds of typical function return points, it's unlikely that
certain registers will be alive, if the code follows the ARM calling
conventions. This might be useful to have as an option, although it's
almost certain that games will break this.
De-aliasing:
For aliased lines (ending in (')), if the target is dead then not only
will that line be dropped, but all future accesses to the aliased version
will use the original version instead. If the target is live but the ALIAS
is dead, then the alias movement will not be made (basically, an application
of the dead target elimination).