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
recurse(opcode_t opcode,int d,int s1,int s2,word v,int cost,insn_t * sequence,int n_insns,word * values,int n_values,const word goal_value,int allowed_cost,int cy,int prune_flags)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 
synth(insn_t * sequence,int n_insns,word * values,int n_values,word goal_value,int allowed_cost,int ci,int prune_hint)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 }
280