1typedef unsigned long int unsigned_word;
2typedef signed long int signed_word;
3typedef unsigned_word word;
4
5typedef enum { ADD, ADD_CI, ADD_CO, ADD_CIO, SUB, SUB_CI, SUB_CO,
6SUB_CIO, ADC_CI, ADC_CO, ADC_CIO, AND, IOR, XOR, ANDC, IORC, EQV,
7NAND, NOR, AND_RC, IOR_RC, XOR_RC, ANDC_RC, IORC_RC, EQV_RC, NAND_RC,
8NOR_RC, AND_CC, IOR_CC, XOR_CC, ANDC_CC, IORC_CC, EQV_CC, NAND_CC,
9NOR_CC, LSHIFTR, ASHIFTR, SHIFTL, LSHIFTR_CO, ASHIFTR_CO, SHIFTL_CO,
10ROTATEL, ROTATEL_CO, ROTATEXL_CIO, ASHIFTR_CON, EXTS1, EXTS2, EXTU1,
11EXTU2, CLZ, CTZ, FF1, FF0, ABSVAL, NABSVAL, CMP, CPEQ, CPGE, CPGEU,
12CPGT, CPGTU, CPLE, CPLEU, CPLT, CPLTU, CPNEQ, CMPPAR, DOZ, COPY,
13EXCHANGE, COMCY, } opcode_t;
14
15typedef 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
23enum prune_flags
24{
25  NO_PRUNE = 0,
26  CY_0 = 1,
27  CY_1 = 2,
28  CY_JUST_SET = 4,
29};
30
31int flag_use_carry = 1;
32
33inline
34recurse(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
82synth(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}
280