|
111
|
1 typedef unsigned long int unsigned_word;
|
|
|
2 typedef signed long int signed_word;
|
|
|
3 typedef unsigned_word word;
|
|
|
4
|
|
|
5 typedef enum { ADD, ADD_CI, ADD_CO, ADD_CIO, SUB, SUB_CI, SUB_CO,
|
|
|
6 SUB_CIO, ADC_CI, ADC_CO, ADC_CIO, AND, IOR, XOR, ANDC, IORC, EQV,
|
|
|
7 NAND, NOR, AND_RC, IOR_RC, XOR_RC, ANDC_RC, IORC_RC, EQV_RC, NAND_RC,
|
|
|
8 NOR_RC, AND_CC, IOR_CC, XOR_CC, ANDC_CC, IORC_CC, EQV_CC, NAND_CC,
|
|
|
9 NOR_CC, LSHIFTR, ASHIFTR, SHIFTL, LSHIFTR_CO, ASHIFTR_CO, SHIFTL_CO,
|
|
|
10 ROTATEL, ROTATEL_CO, ROTATEXL_CIO, ASHIFTR_CON, EXTS1, EXTS2, EXTU1,
|
|
|
11 EXTU2, CLZ, CTZ, FF1, FF0, ABSVAL, NABSVAL, CMP, CPEQ, CPGE, CPGEU,
|
|
|
12 CPGT, CPGTU, CPLE, CPLEU, CPLT, CPLTU, CPNEQ, CMPPAR, DOZ, COPY,
|
|
|
13 EXCHANGE, COMCY, } opcode_t;
|
|
|
14
|
|
|
15 typedef struct
|
|
|
16 {
|
|
|
17 opcode_t opcode:8;
|
|
|
18 unsigned int s1:8;
|
|
|
19 unsigned int s2:8;
|
|
|
20 unsigned int d:8;
|
|
|
21 } insn_t;
|
|
|
22
|
|
|
23 enum prune_flags
|
|
|
24 {
|
|
|
25 NO_PRUNE = 0,
|
|
|
26 CY_0 = 1,
|
|
|
27 CY_1 = 2,
|
|
|
28 CY_JUST_SET = 4,
|
|
|
29 };
|
|
|
30
|
|
|
31 int flag_use_carry = 1;
|
|
|
32
|
|
|
33 inline
|
|
|
34 recurse(opcode_t opcode,
|
|
|
35 int d,
|
|
|
36 int s1,
|
|
|
37 int s2,
|
|
|
38 word v,
|
|
|
39 int cost,
|
|
|
40 insn_t *sequence,
|
|
|
41 int n_insns,
|
|
|
42 word *values,
|
|
|
43 int n_values,
|
|
|
44 const word goal_value,
|
|
|
45 int allowed_cost,
|
|
|
46 int cy,
|
|
|
47 int prune_flags)
|
|
|
48 {
|
|
|
49 insn_t insn;
|
|
|
50
|
|
|
51 allowed_cost -= cost;
|
|
|
52
|
|
|
53 if (allowed_cost > 0)
|
|
|
54 {
|
|
|
55 word old_d;
|
|
|
56
|
|
|
57 old_d = values[d];
|
|
|
58 values[d] = v;
|
|
|
59
|
|
|
60 insn.opcode = opcode;
|
|
|
61 insn.s1 = s1;
|
|
|
62 insn.s2 = s2;
|
|
|
63 insn.d = d;
|
|
|
64 sequence[n_insns] = insn;
|
|
|
65
|
|
|
66 synth(sequence, n_insns + 1, values, n_values,
|
|
|
67 goal_value, allowed_cost, cy, prune_flags);
|
|
|
68
|
|
|
69 values[d] = old_d;
|
|
|
70 }
|
|
|
71 else if (goal_value == v)
|
|
|
72 {
|
|
|
73 insn.opcode = opcode;
|
|
|
74 insn.s1 = s1;
|
|
|
75 insn.s2 = s2;
|
|
|
76 insn.d = d;
|
|
|
77 sequence[n_insns] = insn;
|
|
|
78 test_sequence(sequence, n_insns + 1);
|
|
|
79 }
|
|
|
80 }
|
|
|
81
|
|
|
82 synth(insn_t *sequence,
|
|
|
83 int n_insns,
|
|
|
84 word *values,
|
|
|
85 int n_values,
|
|
|
86 word goal_value,
|
|
|
87 int allowed_cost,
|
|
|
88 int ci,
|
|
|
89 int prune_hint)
|
|
|
90 {
|
|
|
91 int s1, s2;
|
|
|
92 word v, r1, r2;
|
|
|
93 int co;
|
|
|
94 int last_dest;
|
|
|
95
|
|
|
96 if (n_insns > 0)
|
|
|
97 last_dest = sequence[n_insns - 1].d;
|
|
|
98 else
|
|
|
99 last_dest = -1;
|
|
|
100 if (ci >= 0 && flag_use_carry)
|
|
|
101 {
|
|
|
102 for (s1 = n_values - 1; s1 >= 0; s1--)
|
|
|
103 {
|
|
|
104 r1 = values[s1];
|
|
|
105 for (s2 = s1 - 1; s2 >= 0; s2--)
|
|
|
106 {
|
|
|
107 r2 = values[s2];
|
|
|
108
|
|
|
109 if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
|
|
|
110 {
|
|
|
111 if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
|
|
|
112 continue;
|
|
|
113 }
|
|
|
114 do { word __d = ( r1) + ( r2) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0);
|
|
|
115 recurse(ADD_CIO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
116 do { word __d = ( r1) + ( r2) + (( ci)); ( co) = ( ci); (v) = __d; } while (0);
|
|
|
117 recurse(ADD_CI, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
118
|
|
|
119 do { word __d = ( r1) - ( r2) - (( ci)); ( co) = ( ci) ? __d >= ( r1) : __d > ( r1); (v) = __d; } while (0);
|
|
|
120 recurse(SUB_CIO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
121 do { word __d = ( r2) - ( r1) - (( ci)); ( co) = ( ci) ? __d >= ( r2) : __d > ( r2); (v) = __d; } while (0);
|
|
|
122 recurse(SUB_CIO, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
123
|
|
|
124 do { word __d = ( r1) - ( r2) - (( ci)); ( co) = ( ci); (v) = __d; } while (0);
|
|
|
125 recurse(SUB_CI, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
126 do { word __d = ( r2) - ( r1) - (( ci)); ( co) = ( ci); (v) = __d; } while (0);
|
|
|
127 recurse(SUB_CI, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
128
|
|
|
129 }
|
|
|
130 }
|
|
|
131 }
|
|
|
132 for (s1 = n_values - 1; s1 >= 0; s1--)
|
|
|
133 {
|
|
|
134 r1 = values[s1];
|
|
|
135 for (s2 = s1 - 1; s2 >= 0; s2--)
|
|
|
136 {
|
|
|
137 r2 = values[s2];
|
|
|
138
|
|
|
139 if (allowed_cost <= 1)
|
|
|
140 {
|
|
|
141 if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
|
|
|
142 continue;
|
|
|
143 }
|
|
|
144
|
|
|
145 do { word __d = ( r1) + ( r2); ( co) = __d < ( r1); (v) = __d; } while (0);
|
|
|
146 recurse(ADD_CO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
147
|
|
|
148 ((v) = ( r1) + ( r2), ( co) = ( ci));
|
|
|
149 recurse(ADD, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
150
|
|
|
151 do { word __d = ( r1) - ( r2); ( co) = __d > ( r1); (v) = __d; } while (0);
|
|
|
152 recurse(SUB_CO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
153 do { word __d = ( r2) - ( r1); ( co) = __d > ( r2); (v) = __d; } while (0);
|
|
|
154 recurse(SUB_CO, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
155 ((v) = ( r1) - ( r2), ( co) = ( ci));
|
|
|
156 recurse(SUB, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
157 ((v) = ( r2) - ( r1), ( co) = ( ci));
|
|
|
158 recurse(SUB, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
159
|
|
|
160 ((v) = ( r1) & ( r2), ( co) = ( ci));
|
|
|
161 recurse(AND, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
162
|
|
|
163 ((v) = ( r1) | ( r2), ( co) = ( ci));
|
|
|
164 recurse(IOR, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
165
|
|
|
166 ((v) = ( r1) ^ ( r2), ( co) = ( ci));
|
|
|
167 recurse(XOR, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
168
|
|
|
169 ((v) = ( r1) & ~( r2), ( co) = ( ci));
|
|
|
170 recurse(ANDC, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
171 ((v) = ( r2) & ~( r1), ( co) = ( ci));
|
|
|
172 recurse(ANDC, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
173 ((v) = ( r1) | ~( r2), ( co) = ( ci));
|
|
|
174 recurse(IORC, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
175 ((v) = ( r2) | ~( r1), ( co) = ( ci));
|
|
|
176 recurse(IORC, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
177 ((v) = ( r1) ^ ~( r2), ( co) = ( ci));
|
|
|
178 recurse(EQV, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
179
|
|
|
180 }
|
|
|
181 }
|
|
|
182 if (ci >= 0 && flag_use_carry)
|
|
|
183 {
|
|
|
184 for (s1 = n_values - 1; s1 >= 0; s1--)
|
|
|
185 {
|
|
|
186 r1 = values[s1];
|
|
|
187
|
|
|
188 if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
|
|
|
189 {
|
|
|
190
|
|
|
191 if (last_dest >= 0 && s1 != last_dest)
|
|
|
192 continue;
|
|
|
193 }
|
|
|
194
|
|
|
195 do { word __d = ( r1) + ( r1) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0);
|
|
|
196 recurse(ADD_CIO, n_values, s1, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
197
|
|
|
198 do { word __d = ( r1) + ( r1) + (( ci)); ( co) = ( ci); (v) = __d; } while (0);
|
|
|
199 recurse(ADD_CI, n_values, s1, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
200
|
|
|
201 do { word __d = ( r1) + ( -1 ) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0);
|
|
|
202 recurse(ADD_CIO, n_values, s1, (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
203
|
|
|
204 do { word __d = ( r1) + ( 0 ) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0);
|
|
|
205 recurse(ADD_CIO, n_values, s1, (0x20 + 0) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
206 do { word __d = ( 0 ) - ( r1) - (( ci)); ( co) = ( ci) ? __d >= ( 0 ) : __d > ( 0 ); (v) = __d; } while (0);
|
|
|
207 recurse(SUB_CIO, n_values, (0x20 + 0) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
208
|
|
|
209 }
|
|
|
210 }
|
|
|
211 for (s1 = n_values - 1; s1 >= 0; s1--)
|
|
|
212 {
|
|
|
213 r1 = values[s1];
|
|
|
214
|
|
|
215 if (allowed_cost <= 1)
|
|
|
216 {
|
|
|
217 if (last_dest >= 0 && s1 != last_dest)
|
|
|
218 continue;
|
|
|
219 }
|
|
|
220 do { word __d = ( r1) + ( r1); ( co) = __d < ( r1); (v) = __d; } while (0);
|
|
|
221 recurse(ADD_CO, n_values, s1, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
222
|
|
|
223 ((v) = ( r1) & ( 1 ), ( co) = ( ci));
|
|
|
224 recurse(AND, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
225
|
|
|
226 ((v) = ( r1) ^ ( 1 ), ( co) = ( ci));
|
|
|
227 recurse(XOR, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
228
|
|
|
229 ((v) = ( -1 ) - ( r1), ( co) = ( ci));
|
|
|
230 recurse(SUB, n_values, (0x20 + -1) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
231 do { word __d = ( r1) + ( 1 ); ( co) = __d < ( r1); (v) = __d; } while (0);
|
|
|
232 recurse(ADD_CO, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
233 ((v) = ( r1) + ( 1 ), ( co) = ( ci));
|
|
|
234 recurse(ADD, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
235 do { word __d = ( r1) + ( -1 ); ( co) = __d < ( r1); (v) = __d; } while (0);
|
|
|
236 recurse(ADD_CO, n_values, s1, (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
237 do { word __d = ( r1) - ( 1 ); ( co) = __d > ( r1); (v) = __d; } while (0);
|
|
|
238 recurse(SUB_CO, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
239 do { word __d = ( 0 ) - ( r1); ( co) = __d > ( 0 ); (v) = __d; } while (0);
|
|
|
240 recurse(SUB_CO, n_values, (0x20 + 0) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET);
|
|
|
241 ((v) = ( 0 ) - ( r1), ( co) = ( ci));
|
|
|
242 recurse(SUB, n_values, (0x20 + 0) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
243 ((v) = ((unsigned_word) ( r1) >> (( 1 ) & (32 - 1)) ), ( co) = ( ci));
|
|
|
244 recurse(LSHIFTR, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
245 ((v) = ((signed_word) ( r1) >> (( 1 ) & (32 - 1)) ), ( co) = ( ci));
|
|
|
246 recurse(ASHIFTR, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
247 ((v) = ((signed_word) ( r1) << (( 1 ) & (32 - 1)) ), ( co) = ( ci));
|
|
|
248 recurse(SHIFTL, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
249 ((v) = ((unsigned_word) ( r1) >> (( 32 -1 ) & (32 - 1)) ), ( co) = ( ci));
|
|
|
250 recurse(LSHIFTR, n_values, s1, (0x20 + 32 -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
251 ((v) = ((signed_word) ( r1) >> (( 32 -1 ) & (32 - 1)) ), ( co) = ( ci));
|
|
|
252 recurse(ASHIFTR, n_values, s1, (0x20 + 32 -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
253 }
|
|
|
254 if (ci >= 0 && flag_use_carry
|
|
|
255 && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
|
|
|
256 {
|
|
|
257 do { word __d = ( 0 ) + ( 0 ) + (( ci)); ( co) = ( ci) ? __d <= ( 0 ) : __d < ( 0 ); (v) = __d; } while (0);
|
|
|
258 recurse(ADD_CIO, n_values, (0x20 + 0) , (0x20 + 0) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET | CY_0);
|
|
|
259 do { word __d = ( 0 ) - ( 0 ) - (( ci)); ( co) = ( ci) ? __d >= ( 0 ) : __d > ( 0 ); (v) = __d; } while (0);
|
|
|
260 recurse(SUB_CIO, n_values, (0x20 + 0) , (0x20 + 0) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
261 do { word __d = ( 0 ) - ( -1 ) - (( ci)); ( co) = ( ci) ? __d >= ( 0 ) : __d > ( 0 ); (v) = __d; } while (0);
|
|
|
262 recurse(SUB_CIO, n_values, (0x20 + 0) , (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET | CY_1);
|
|
|
263 do { word __d = ( 0 ) + ( -1 ) + (( ci)); ( co) = ( ci) ? __d <= ( 0 ) : __d < ( 0 ); (v) = __d; } while (0);
|
|
|
264 recurse(ADD_CIO, n_values, (0x20 + 0) , (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
265
|
|
|
266 }
|
|
|
267
|
|
|
268 if (allowed_cost > 1)
|
|
|
269 {
|
|
|
270 ((v) = ( 0x80000000 ), ( co) = ( ci));
|
|
|
271 recurse(COPY, n_values, (0x20 - 2) , 0, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
272
|
|
|
273 ((v) = ( -1 ), ( co) = ( ci));
|
|
|
274 recurse(COPY, n_values, (0x20 + -1) , 0, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
275
|
|
|
276 ((v) = ( 1 ), ( co) = ( ci));
|
|
|
277 recurse(COPY, n_values, (0x20 + 1) , 0, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET);
|
|
|
278 }
|
|
|
279 }
|
