-
Notifications
You must be signed in to change notification settings - Fork 6
/
TODO
162 lines (123 loc) · 7.34 KB
/
TODO
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
* For the 960, we often see sequences "chkbit;concmp" where the chkbit is
just used to unconditionally clear bit 2 of Ac.cc. We might want to prune
the variants of chkbit to decrease the number of printed sequences.
* For the 960, we pass the prune hints based on bit 1 of the Ac.cc. This
might lead to undesirable pruning.
* For the 960 and Alpha, we let conditionally executed instructions like
ADDO_cc_960, SUBO_cc_960, and CMOVEcc overwrite an existing register.
This is OK, but we should also write to a new register, since several
conditional adds and subtracts with different conditions and the same
destination register might make the result well-defined anyway.
* When we have conditional execution (HPPA, i960, Alpha, Sparc9, Coldfire,
etc) we have to make sure we prune instruction 3 carefully in this
situation:
insn1
insn2 is conditionally executed
insn3
Depending on the flag settings of insn1 and insn2, the correct set of
insn3 to try is tricky. Now, we might prune too much.
* Later 29k models have additional logical ops. Add them!
* add_co(a,a) and shiftl_co(a,1) are identical. Affects m68k, x86, pyr, etc.
* For goal functions with the same arity, the exact same computations are
made in synth. This suggests that we could search for many goal functions
in parallel instead of serially. We could maintain an array of goal
values, one for each goal. Instead of simply comparing the last generated
value to goal_value, we would loop through a goal_values[] array, and call
test_sequence for each goal that matches. This would speed up searches by
as much as a factor of 10.
* Adding the bsfl instruction revealed a deficiency: We can't deal with
instructions that give an undefined result for some inputs. This is so
because the sequences might fail to work only when the undefined result
happen to become a certain value. To cope with this, we have to make
test_sequence try lots of values, but it can only do that if it knows
about these instructions.
A cleaner way would be to add a valid bit to each computed value.
* Now we require equality between a computed goal value and a computed
result. Permit fuzzier function, like "something negative". E.g., a
fuzzy sgn function might be useful.
* Most importantly: Generalize the class of possible goal functions. Allow
them to be any mapping from a vector of words to another vector of words,
each of arbitrary length.
To make it fast, record after each instruction if it generates a value
that is in (the vector) goal_value, and prune a sequence if it has not
produced N-M requested values when M more instructions are allowed [N the
number of words in goal_value].
We should split `synth'. The leaf search `synth' function could be
written like currently, but with the leaf-test "if (allowed_cost > 0)"
removed. The non-leaf `synth' need to loop and look for the generated
value in goal_value. To avoid massive code replication, we have to put
the synth function in a separate file, and play with cpp and #include.
Make sure to handle the case were you find all values before the last
instruction. This might be non-trivial! We know that we have to use the
value from the ultimate instruction, otherwise we would have found this
sequence before. Problem is, we will either have to loop and look for
the value in goal_value, or, probably much better, just accept the
sequence.
* Add -test-on-cpu option triggering a mechanism for testing the generated
sequences on the real hardware. That would help debug the simulation
code.
* I'd like to have a means to define that a goal function is not defined
for all possible input values. An extra parameter, ALLOWED_ARGUMENTS, to
DEF_GOAL could take care of that.
Also I'd like the user to have the possibility to add a list of immediate
values to try for each goal function. For example, 31 and 32 could be
useful for ffs.
* Make it possible to handle more immediate values, for example by putting
them in the immediate_val array.
* Interpret goal functions so the user doesn't need to recompile.
Interpretation would make goal function evaluation slower than it is now,
but goal function evaluation is not critical.
* Add code to algebraically prove that generated sequences are correct.
* Add bsrl/bsfl and bfffo to CISC synth.
* Check that PERFORM_CLZ works like RS/6000's cntlz and 29k's clz. Is it
ok for input == 0?
* A major speed improvement would be to make independent insn have a
canonical order. Consider `gts' on the SPARC. This is probably not very
hard, if insns are enumerated in some clever way and loop variables are
passed down. A very simple but potentially quite powerful mechanism: If
the putative instruction doesn't depend on the last instruction, compare
the putative instruction's opcode with the last instruction's opcode, and
proceed iff, say, the < relation holds.
After an instruction that sets carry (and there is another instruction
with the same effect apart from that it doesn't affect carry), the
generated carry has to be used. [Fix this with a reservation vector
--allow both making and deleting a reservation. Make reservation when
carry is generated and delete it when it is used.] The leaf instructions
have to input carry if an unused carry is pending.
Make sure all computed values are used by subsequent instructions. For
example, if we have just two more values to compute and three yet unused
values, the last two instructions have to restrict their input operands.
* Efficient pruning of sequences not using generated resources:
Each generated instruction should record it's computed 'resources' in a
list of unused resources. (A written register is such a resource, and the
carry flag is such a resource.) When a resource is used by an
instruction, it's removed from the data base.
At each recursion, we check that the unused resources can be consumed
with the allowed number of instructions. If not, we back-track.
Beware: A resource is not 'consumed' when it has been used. I have seen
optimal sequences that uses a generated carry more than once.
* Shift 32 steps on 68k is well-defined. LSHIFTR_CO can be used to zero a
word and simultaneously move the sign bit to the X flag, ASHIFTR_CO can
be used to propagate the sign bit to the whole word and to the X flag.
Useful?
* Model the exact timing, i.e., instruction overlap, superscalar issue,
etc. Requires modelling the CPU internal function units.
* `386: bt, clc, cmc, cdq[0->1], lea, shld, shrd, stc.
* Make the instruction description cleaner. Something of this kind would
be great:
88k:
{ADD, "addu %d{r},%1{r,0},%2{r,[0-FFFF]}"},
{ADD_CI, "addu.ci %d{r},%1{r,0},%2{r,[0-FFFF]}"},
...
sparc:
{ADD, "add %1{r,0},%2{r,[-1000,+FFF]},%d{r}"},
{ADD_CI, "addx %1{r,0},%2{r,[-1000,+FFF]},%d{r}"},
...
We would need a tool to extract the information and generate a 'synth'
function. (That instruction description format would be useful to
assemblers, disassemblers, and simulators too.)
* Include a 'synth' function for several targets in one gso binary. Have a
command line option -t<target> select which one to use.
* The following XCore instructions are missing: crc, crc8, ladd, lmul, lsub,
maccs, maccu. In addition not all possible immediate values for the add, eq,
ldaw, ldc, mkmsk, sext, sub and zext instructions are used.