1 /*
2 * UAE - The Un*x Amiga Emulator
3 *
4 * Optimized blitter minterm function generator
5 *
6 * Copyright 1995,1996 Bernd Schmidt
7 * Copyright 1996 Alessandro Bissacco
8 *
9 * Overkill, n: cf. genblitter
10 */
11
12 #include "sysconfig.h"
13 #include "sysdeps.h"
14
15 #include "options.h"
16
17 static void nop(int);
18
19 #define xmalloc malloc
20 #define xfree free
21 #define xrealloc realloc
22
23 typedef struct tree_n {
24 enum tree_op { op_and, op_or, op_xor, op_not, op_a, op_b, op_c, op_d, op_e, op_f } op;
25 struct tree_n *left, *right;
26 } *tree;
27
28 static struct tree_n TRA = { op_a, NULL, NULL };
29 static struct tree_n TRB = { op_b, NULL, NULL };
30 static struct tree_n TRC = { op_c, NULL, NULL };
31 static struct tree_n TRD = { op_d, NULL, NULL };
32 static struct tree_n TRE = { op_e, NULL, NULL };
33 static struct tree_n TRF = { op_f, NULL, NULL };
34 static tree tree_a = &TRA;
35 static tree tree_b = &TRB;
36 static tree tree_c = &TRC;
37 static tree tree_d = &TRD;
38 static tree tree_e = &TRE;
39 static tree tree_f = &TRF;
40
41 typedef struct {
42 tree *trees;
43 int space;
44 int ntrees;
45 } tree_vec;
46
issrc(tree t)47 STATIC_INLINE int issrc (tree t)
48 {
49 return t == tree_a || t == tree_b || t == tree_c || t == tree_d || t == tree_e || t == tree_f;
50 }
51
new_op_tree(enum tree_op op,tree l,tree r)52 static tree new_op_tree(enum tree_op op, tree l, tree r)
53 {
54 tree t;
55 if (op == op_not && l->op == op_not) {
56 t = l->left;
57 xfree(l);
58 return t;
59 }
60 t = (tree)xmalloc(sizeof(struct tree_n));
61 t->left = l;
62 t->right = r;
63 t->op = op;
64 return t;
65 }
66
opidx(tree t)67 static int opidx (tree t)
68 {
69 switch (t->op) {
70 case op_a:
71 return 0;
72 case op_b:
73 return 1;
74 case op_c:
75 return 2;
76 case op_d:
77 return 3;
78 case op_e:
79 return 4;
80 case op_f:
81 return 5;
82 default:
83 return -1;
84 }
85 }
86
tree_cst(tree t,unsigned int * src,unsigned int * notsrc)87 static int tree_cst (tree t, unsigned int *src, unsigned int *notsrc)
88 {
89 int idx = opidx (t);
90 if (idx >= 0) {
91 src[idx] = 1;
92 return 0;
93 }
94 switch (t->op) {
95 case op_not:
96 idx = opidx (t->left);
97 if (idx >= 0) {
98 notsrc[idx] = 1;
99 return 3;
100 }
101 return 3 + tree_cst (t->left, src, notsrc);
102
103 case op_and:
104 case op_xor:
105 case op_or:
106 return 4 + tree_cst (t->left, src, notsrc) + tree_cst (t->right, src, notsrc);
107
108 default:
109 abort ();
110 }
111 }
112
tree_cost(tree t)113 static int tree_cost (tree t)
114 {
115 int i, cost;
116 unsigned int src[6], notsrc[6];
117 memset (src, 0, sizeof src);
118 memset (notsrc, 0, sizeof notsrc);
119
120 cost = tree_cst (t, src, notsrc);
121 for (i = 0; i < 6; i++)
122 if (src[i] && notsrc[i])
123 cost++;
124 return cost;
125 }
126
add_vec(tree_vec * tv,tree t)127 static int add_vec(tree_vec *tv, tree t)
128 {
129 int i;
130 #if 0
131 if (! tree_isnormal(t))
132 nop(2);
133 #endif
134 if (tv->ntrees == tv->space) {
135 tv->trees = (tree *)xrealloc(tv->trees, sizeof(tree)*(tv->space += 40));
136 }
137 tv->trees[tv->ntrees++] = t;
138
139 return 1;
140 }
141
init_vec(tree_vec * tv)142 static void init_vec(tree_vec *tv)
143 {
144 tv->ntrees = tv->space = 0;
145 tv->trees = NULL;
146 }
147
do_sprint_tree(char * s,tree t)148 static void do_sprint_tree (char *s, tree t)
149 {
150 enum tree_op op = t->op;
151 switch (op) {
152 case op_a:
153 strcat (s, "srca");
154 break;
155 case op_b:
156 strcat (s, "srcb");
157 break;
158 case op_c:
159 strcat (s, "srcc");
160 break;
161 case op_d:
162 strcat (s, "srcd");
163 break;
164 case op_e:
165 strcat (s, "srce");
166 break;
167 case op_f:
168 strcat (s, "srcf");
169 break;
170
171 case op_and:
172 case op_or:
173 case op_xor:
174 {
175
176 char *c = op == op_and ? " & " : op == op_or ? " | " : " ^ ";
177 strcat (s, "(");
178 do_sprint_tree (s, t->left);
179 strcat (s, c);
180 while (t->right->op == op) {
181 t = t->right;
182 do_sprint_tree (s, t->left);
183 strcat (s, c);
184 }
185 do_sprint_tree(s, t->right);
186 strcat (s, ")");
187 }
188 break;
189
190 case op_not:
191 strcat (s, "~");
192 do_sprint_tree (s, t->left);
193 break;
194 }
195 }
196
197 static tree_vec size_trees[20];
198
199 static struct tree_n bad_tree = { op_and, &bad_tree, &bad_tree };
200
201 static unsigned int used_mask[256];
202 static tree best_trees[256];
203 static unsigned int best_cost[256];
204 static int n_unknown;
205
which_fn(tree t)206 static unsigned long which_fn (tree t)
207 {
208 switch (t->op) {
209 case op_a:
210 return 0xf0;
211 case op_b:
212 return 0xcc;
213 case op_c:
214 return 0xaa;
215 case op_and:
216 return which_fn (t->left) & which_fn (t->right);
217 case op_or:
218 return which_fn (t->left) | which_fn (t->right);
219 case op_xor:
220 return which_fn (t->left) ^ which_fn (t->right);
221 case op_not:
222 return 0xFF & ~which_fn (t->left);
223 default:
224 abort ();
225 }
226 }
227
tree_used_mask(tree t)228 static unsigned long tree_used_mask (tree t)
229 {
230 switch (t->op) {
231 case op_a:
232 return 1;
233 case op_b:
234 return 2;
235 case op_c:
236 return 4;
237 case op_and:
238 case op_or:
239 case op_xor:
240 return tree_used_mask (t->left) | tree_used_mask (t->right);
241 case op_not:
242 return tree_used_mask (t->left);
243 default:
244 abort ();
245 }
246 }
247
candidate(tree_vec * v,tree t)248 static void candidate (tree_vec *v, tree t)
249 {
250 unsigned long fn = which_fn (t);
251 unsigned int cost = tree_cost (t);
252 if (best_trees[fn] == 0)
253 n_unknown--;
254 if (cost < best_cost[fn])
255 best_trees[fn] = t, best_cost[fn] = cost;
256 add_vec (v, t);
257 }
258
cand_and_not(tree_vec * v,tree t)259 static void cand_and_not (tree_vec *v, tree t)
260 {
261 candidate (v, t);
262 t = new_op_tree (op_not, t, 0);
263 candidate (v, t);
264 }
265
try_tree(tree_vec * v,tree t)266 static void try_tree (tree_vec *v, tree t)
267 {
268 int fnl = which_fn (t->left);
269 int fnr = which_fn (t->right);
270 int fn = which_fn (t);
271 if (fn == fnl
272 || fn == fnr
273 || fn == 0
274 || fn == 0xFF
275 || (tree_used_mask (t) & ~used_mask[fn]) != 0
276 || best_cost[fn] + 6 < tree_cost (t))
277 {
278 xfree (t);
279 return;
280 }
281 cand_and_not (v, t);
282 }
283
find_best_trees(void)284 static void find_best_trees (void)
285 {
286 int i, size, do_stop;
287 for (i = 0; i < 256; i++) {
288 best_trees[i] = i == 0 || i == 255 ? &bad_tree : 0;
289 best_cost[i] = 65535;
290 }
291 n_unknown = 254;
292
293 init_vec (size_trees);
294 cand_and_not (size_trees, tree_a);
295 cand_and_not (size_trees, tree_b);
296 cand_and_not (size_trees, tree_c);
297
298 do_stop = 0;
299 for (size = 2; ! do_stop && size < 20; size++) {
300 int split, last_split;
301 tree_vec *sv = size_trees + size - 1;
302
303 if (n_unknown == 0)
304 do_stop = 1;
305 last_split = (size >> 1) + 1;
306 for (split = 1; split < last_split; split++) {
307 int szl = split;
308 int szr = size - split;
309 tree_vec *lv = size_trees + szl - 1;
310 tree_vec *rv = size_trees + szr - 1;
311 int i;
312
313 for (i = 0; i < lv->ntrees; i++) {
314 tree l = lv->trees[i];
315 int j;
316 for (j = szl == szr ? i + 1 : 0; j < rv->ntrees; j++) {
317 tree r = rv->trees[j];
318
319 if (l->op != op_and || r->op != op_and) {
320 tree tmp = (l->op == op_and
321 ? new_op_tree (op_and, r, l)
322 : new_op_tree (op_and, l, r));
323 try_tree (sv, tmp);
324 }
325 if (l->op != op_or || r->op != op_or) {
326 tree tmp = (l->op == op_or
327 ? new_op_tree (op_or, r, l)
328 : new_op_tree (op_or, l, r));
329 try_tree (sv, tmp);
330 }
331 if (l->op != op_xor || r->op != op_xor) {
332 tree tmp = (l->op == op_xor
333 ? new_op_tree (op_xor, r, l)
334 : new_op_tree (op_xor, l, r));
335 try_tree (sv, tmp);
336 }
337 }
338 }
339 }
340 /* An additional pass doesn't seem to create better solutions
341 * (not that much of a surprise). */
342 if (n_unknown == 0)
343 do_stop = 1;
344 }
345 }
346
bitset(int mt,int bit)347 static int bitset (int mt, int bit)
348 {
349 return mt & (1 << bit);
350 }
351
generate_expr(int minterm)352 static unsigned int generate_expr (int minterm)
353 {
354 int bits = 0;
355 int i;
356 int expr_dc[8], nexp = 0;
357 int expr_used[8];
358
359 if (minterm == 0 || minterm == 0xFF)
360 return 0;
361
362 for (i = 0; i < 8; i++) {
363 if (bitset (minterm, i) && !bitset (bits, i)) {
364 int j;
365 int dontcare = 0;
366 int firstand = 1;
367 int bitbucket[8], bitcount;
368
369 bits |= 1<<i;
370 bitcount = 1; bitbucket[0] = i;
371 for(j=1; j<8; j *= 2) {
372 int success = 1;
373 int k;
374 for(k=0; k < bitcount; k++) {
375 if (!bitset (minterm, bitbucket[k] ^ j)) {
376 success = 0;
377 }
378 }
379 if (success) {
380 int l;
381 dontcare |= j;
382 for(l=bitcount; l < bitcount*2; l++) {
383 bitbucket[l] = bitbucket[l-bitcount] ^ j;
384 bits |= 1 << bitbucket[l];
385 }
386 bitcount *= 2;
387 }
388 }
389 expr_used[nexp] = 1;
390 expr_dc[nexp] = dontcare;
391 nexp++;
392 }
393 }
394
395 {
396 unsigned int result = 0;
397 for (i = 0; i < nexp; i++) {
398 int j;
399
400 for (j = 1; j < 8; j *= 2) {
401 if (!(expr_dc[i] & j))
402 result |= (j == 1 ? 4 : j == 2 ? 2 : 1);
403 }
404 }
405 return result;
406 }
407 }
408
print_tree(tree t)409 static void print_tree(tree t)
410 {
411 char buf[300] = "";
412 do_sprint_tree (buf, t);
413 printf ("%s", buf);
414 }
415
generate_optable(void)416 static void generate_optable(void)
417 {
418 int minterm;
419 printf(" /* This file generated automatically - do not edit */\n\n");
420 printf("#include \"genblitter.h\"\n\n");
421 printf("struct blitop blitops[256] = {\n");
422 for (minterm = 0; minterm < 256; minterm++) {
423 printf(" /* %02x */ { \"", minterm);
424 if (minterm == 0)
425 printf ("0");
426 else if (minterm == 255)
427 printf ("0xFFFFFFFF");
428 else
429 print_tree (best_trees[minterm]);
430
431 printf("\", %d }%s\n", used_mask[minterm], minterm == 255 ? "" : ",");
432 fflush(stdout);
433 }
434 printf("};\n");
435 }
436
main(int argc,char ** argv)437 int main (int argc, char **argv)
438 {
439 int minterm;
440 for (minterm = 0; minterm < 256; minterm++)
441 used_mask[minterm] = generate_expr (minterm);
442 find_best_trees ();
443 generate_optable ();
444
445 return 0;
446 }
447
nop(int a)448 void nop(int a)
449 {
450 }
451
452