-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathoptimize.cpp
118 lines (98 loc) · 2.85 KB
/
optimize.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include "instructions2.h"
enum class used_variables : uint64_t {
absolute = 0xF,
absolute0 = 0x1,
absolute1 = 0x2,
absolute2 = 0x4,
absolute3 = 0x8,
zp = 0xF0,
zp0 = 0x10,
zp1 = 0x20,
zp2 = 0x40,
zp3 = 0x80,
immediate = 0xF00,
immediate0 = 0x100,
immediate1 = 0x200,
immediate2 = 0x400,
immediate3 = 0x800,
};
/*
NEEDS:
- Canonicalization and rewriting of instruction sequences.
- SSA form of instruction sequence, to allow building a dag of instruction orderings.
Canonicalization:
for example, the instruction sequence:
lda #1
ldx #0
sta absolute0, x
ldx #1
stx absolute0
Can be represented like this:
a0, s0, n0, mem0 = start()
a1, s1, n1 = lda(#1)
x1, s2, n2 = ldx(#0)
mem1 = sta(a1, absolute0, x1, mem0)
x2, s3, n3 = ldx(#1)
mem2 = stx(x2, absolute0, mem1)
end(mem2, a1, x2, s3, n3)
a0 s0 n0 mem0 = start()
| | | |
x x x |
|
a1 s1 n1 | = lda(#1)
\ | | |
\ x x |
+--------------------+
x1 | s2 n2 | = ldx(#0)
| | | | \
x \ x x ---------+---------------+
----------------- | |
mem1 \ = sta(a1, absolute0, mem0)
\ |
+----------------)---------------------------+
| |
x2 s3 n3 | = ldx(#1) |
\ | | | |
\ | | | |
------)------)----)---+-------- |
| | | | \
mem2 | | | | = sta(x2, absolute0, mem1)
\ | | | |
------+------+----+---+---------+----+---+---+---+
| | | | |
end(mem2, a1, x2, s3, n3)
Which forms this dag:
o
/ \
+---- ----+
lda(#1) ldx(#0)
| |
sta(absolute0, x)
|
ldx(#1)
|
stx(absolute0)
A topological sort of this graph gives
all of the possible orderings of the instructions,
which doesn't leave much room for changes.
Now, we can apply optimizations:
1. "ldx #0 ; sta absolute0, x", where x is not live,
is the same as sta absolute0.
o
/ \
+--- ----+
lda(#1) ldx(#1)
| |
sta(absolute0) |
| |
stx(absolute0)
2. "lda #1 ; ldx #1" is "lda #1 ; tax"
lda #1
tax
sta absolute0
stx absolute0
3. "sta absolute0 ; stx absolute0" is "stx absolute0"
lda #1
tax
stx absolute0
*/