0: 1: 2: 3:
ldr r1, [pc, #37] ldr r1, [pc, #37] ldr r1, [pc, #37] ldr r1, [pc, #37]
add r0, r4, r1 add r0, r4, r1 add r0, r4, r1
ldrb r0, [r0, #0] ldrb r0, [r0] ldrb r0, [r4, r1] ldrb r0, [r4, r1]
mov r1, #3 mov r1, #3 mov r1, #3
and r1, r0 and r1, r1, r0 and r1, r0, #3 and r1, r0, #3
mov r2, #188 mov r2, #188 mov r2, #188
lsl r2, r2, #1 mov r2, r2, lsl #1 mov r2, #376
add r0, r4, r2 add r0, r4, r2 add r0, r4, #376
ldrh r5, [r0, #0] ldrh r5, [r0] ldrh r5, [r4, #376] ldrh r5, [r4, #376]
mov r0, r4 mov r0, r4 mov r0, r4
add r0, #76 add r0, r0, #76 add r0, r4, #76
ldrb r0, [r0, #0] ldrb r0, [r0] ldrb r0, [r4, #76] ldrb r0, [r4, #76]
mov r6, #7 mov r6, #7 mov r6, #7
and r6, r0 and r6, r6, r0 and r6, r0, #7 and r6, r0, #7
mov r3, #186 mov r3, #186 mov r3, #186
lsl r3, r3, #1 mov r3, r3, lsl #1 mov r3, #376
add r0, r4, r3 add r0, r4, r3 add r0, r4, #376
ldr r2, [r0, #0] ldr r2, [r0] ldr r2, [r4, #376] ldr r2, [r4, #376]
mov r0, r4 mov r0, r4 mov r0, r4
add r0, #154 add r0, r0, #154 add r0, r4, #154
ldrb r3, [r0, #0] ldrb r3, [r0] ldrb r3, [r4, #154] ldrb r3, [r4, #154]
mov r7, #15 mov r7, #15 mov r7, #15 mov r7, #15
mov r0, r7 mov r0, r7 mov r0, #15
and r0, r3 and r0, r0, r3 and r0, r3, #15 and r0, r3, #15
lsl r0, r0, #2 mov r0, r0, lsl #2 mov r0, r0, lsl #2 (')
add r1, r1, r0 add r1, r1, r0 add r1, r1, r0', lsl #2 add r1, r1, r0, lsl #2
lsl r0, r6, #2 mov r0, r6, lsl #2 mov r0, r6, lsl #2
add r0, r0, r6 add r0, r0, r6 add r0, r6, r6 lsl #2 add r0, r6, r6 lsl #2
lsl r0, r0, #2 mov r0, r0, lsl #2 mov r0, r0, lsl #2 (')
add r1, r1, r0 add r1, r1, r0 add r1, r1, r0', lsl #2 add r1, r1, r0, lsl #2
add r2, #128 add r2, r2, #128 add r2, r2, #128 add r2, r2, #128
add r2, r2, r1 add r2, r2, r1 add r2, r2, r1 (')
ldrb r0, [r2, #0] ldrb r0, [r2] ldrb r0, [r2', r1] ldrb r0, [r2, r1]
lsl r2, r0, #4 mov r2, r0, lsl #4 mov 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 mov r5, #16 mov r5, #16 mov r5, #16
l1: l1: l1:
lsl r0, r5, #1 mov r0, r2, lsl #1 mov 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 add r1, r4, r3 add r1, r4, r3
ldrb r1, [r1, #0] ldrb r1, [r1] ldrb r1, [r4, r3] ldrb r1, [r4, r3]
add r1, r2, r1 add r1, r2, r1 add r1, r2, r1 add r1, r2, r1
add r1, r1, r0 add r1, r1, r0 add r1, r1, r0 add r1, r1, r0
mov r0, r4 mov r0, r4 mov r0, r4
add r0, #188 add r0, r0, #188 add r0, r4, #188
ldr r2, [r0, #0] ldr r2, [r0] ldr r2, [r4, #188] ldr r2, [r4, #188]
mov r0, r2 mov r0, r2 mov 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 add r0, r2, r3 add 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 sub r0, r1, r0 sub 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 mov r0, r2, asr #16 mov 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 mov r0, r1 mov r0, r1 mov r0, r1
l3: l3: l3:
asr r2, r0, #6 mov r2, r0, asr #6 mov r2, r0, asr #6
and r2, r7 and r2, r2, r7 and r2, r7, r0, asr #6 and r2, r7, r0, asr #6
mov r3, r4 mov r3, r4 mov r3, r4
add r3, #192 add r3, r3, #192 add r3, r4, #192 add r3, r4, #192
mov r1, #186 mov r1, #186 mov r1, #186
lsl r1, r1, #1 mov r1, r1, lsl #1 mov r1, #372
add r0, r4, r1 add r0, r4, r1 add r0, r4, #372
ldr r0, [r0, #0] ldr r0, [r0] ldr r0, [r4, #372] ldr r0, [r4, #372]
lsl r1, r6, #4 mov r1, r6, lsl #4 mov r1, r6, lsl #4 mov r1, r6, lsl #4
add r2, r2, r1 add r2, r2, r1 add r2, r2, r6, lsl #4 add r2, r2, r6, lsl #4
add r0, r0, r2 add r0, r0, r2 add r0, r0, r2 (')
ldrb r0, [r0, #0] ldrb r0, [r0] ldrb r0, [r0', r2] ldrb r0, [r0, r2]
lsl r0, r0, #12 mov r0, r0, lsl #12 mov r0, r0, lsl #12 (') mov 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 propogation 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
propgation.
Pass 2: Propogation and aliasing
Here, register propogation. Propogation 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 clearly with the following
examples. Naturally, it only makes sense to propogate values to the point
where they may still be useful, so the following propogations are
performed:
Move propogation:
When register a is moved to register b, register a will be referenced
instead of register b later on.
mov r0, r1 < "r1" propogates to r0
add r0, r0, r1 < r0 is substituted with "r1"
add r0, r0, r0 < the first propogation is now dead
This becomes:
mov r0, r1
add r0, r1, r1
add r0, r0, r0
Constant propogation:
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.
mov r0, #1
add r0, r1, r0
Becomes:
mov r0, #1
add r0, r1, #1
Shift propogation:
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.
mov r0, r1, lsl #2
add r0, r1, r0
Becomes:
mov r0, r1, lsl #2
add r0, r1, r1, lsl #2
Addition/subtraction propogation:
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].
add r0, r1, r2
ldr r0, [r0]
Becomes:
add r0, r1, r2
ldr r0, [r1, r2]
Add/sub + shift propgation:
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 propogation:
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 propogation 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.
mov r0, r1, lsl #2
sub r0, r0, r1
Becomes:
mov r0, r1, lsl #2
rsb 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)
mov r0, #2
add r0, r0, #2
Becomes:
mov r0, #2
mov 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 propogations more complex than simple move or
constant propogation (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 propogation
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 propogation 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.
mov r0, r0, lsl #1
add r0, r1, r0
Becomes:
mov r0, r0, lsl #1 (')
add r0, r1, r0', lsl #1
The line:
mov r0, r0, lsl #1 (')
Can be thought of as:
mov r0', r0
mov 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 is "alive" at
any point afterwards. What this means is that the register is used
somewhere later on in the block before it is overwritten. Of course,
this only applies to lines with a destination register, but almost all
have one.
For instance:
mov r0, r1 < r0 is dead here because it's overwritten
mov r0, #5 < here before it's ever used
On the other hand:
add r0, r1, r2 < r0 is alive here because it's used
add r3, r0, r4 < as a source here
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.
mov r0, #5
add r0, r1, #5
Becomes:
add r0, r1, #5
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).