Commit | Line | Data |
---|---|---|
cac4f7ea DR |
1 | # |
2 | /* | |
3 | * C compiler part 2 -- expression optimizer | |
4 | * | |
5 | */ | |
6 | ||
7 | #include "c1h.c" | |
8 | ||
9 | optim(atree) | |
10 | struct tnode *atree; | |
11 | { | |
12 | register op, dope; | |
13 | int d1, d2; | |
14 | struct tnode *t; | |
15 | register struct tnode *tree; | |
16 | ||
17 | if ((tree=atree)==0) | |
18 | return(0); | |
19 | if ((op = tree->op)==0) | |
20 | return(tree); | |
21 | if (op==NAME && tree->class==AUTO) { | |
22 | tree->class = OFFS; | |
23 | tree->regno = 5; | |
24 | tree->offset = tree->nloc; | |
25 | } | |
26 | dope = opdope[op]; | |
27 | if ((dope&LEAF) != 0) | |
28 | return(tree); | |
29 | if ((dope&BINARY) == 0) | |
30 | return(unoptim(tree)); | |
31 | /* is known to be binary */ | |
32 | if (tree->type==CHAR) | |
33 | tree->type = INT; | |
34 | if ((dope&COMMUTE)!=0) { | |
35 | acomm: d1 = tree->type; | |
36 | tree = acommute(tree); | |
37 | tree->type = d1; | |
38 | /* | |
39 | * PDP-11 special: | |
40 | * replace a&b by a NAND ~ b. | |
41 | * This will be undone when in | |
42 | * truth-value context. | |
43 | */ | |
44 | if (tree->op!=AND) | |
45 | return(tree); | |
46 | tree->op = NAND; | |
47 | tree->tr2 = block(1, COMPL, tree->tr2->type, 0, tree->tr2); | |
48 | } | |
49 | again: | |
50 | tree->tr1 = optim(tree->tr1); | |
51 | tree->tr2 = optim(tree->tr2); | |
52 | if ((dope&RELAT) != 0) { | |
53 | if ((d1=degree(tree->tr1)) < (d2=degree(tree->tr2)) | |
54 | || d1==d2 && tree->tr1->op==NAME && tree->tr2->op!=NAME) { | |
55 | t = tree->tr1; | |
56 | tree->tr1 = tree->tr2; | |
57 | tree->tr2 = t; | |
58 | tree->op = maprel[op-EQUAL]; | |
59 | } | |
60 | if (tree->tr1->type==CHAR && tree->tr2->op==CON | |
61 | && (dcalc(tree->tr1) <= 12 || tree->tr1->op==STAR) | |
62 | && tree->tr2->value <= 127 && tree->tr2->value >= 0) | |
63 | tree->tr2->type = CHAR; | |
64 | } | |
65 | d1 = max(degree(tree->tr1), islong(tree->type)); | |
66 | d2 = max(degree(tree->tr2), 0); | |
67 | if (tree->tr1->type==LONG && dope&RELAT) | |
68 | d1 = 10; | |
69 | switch (op) { | |
70 | ||
71 | case LTIMES: | |
72 | case LDIV: | |
73 | case LMOD: | |
74 | case LASTIMES: | |
75 | case LASDIV: | |
76 | case LASMOD: | |
77 | tree->degree = 10; | |
78 | break; | |
79 | ||
80 | /* | |
81 | * PDP-11 special: | |
82 | * generate new =&~ operator out of =& | |
83 | * by complementing the RHS. | |
84 | */ | |
85 | case ASSAND: | |
86 | op = ASSNAND; | |
87 | tree->op = op; | |
88 | tree->tr2 = block(2, COMPL, tree->tr2->type, 0, tree->tr2); | |
89 | goto again; | |
90 | ||
91 | case NAND: | |
92 | if (isconstant(tree->tr2) && tree->tr2->value==0) | |
93 | return(tree->tr1); | |
94 | goto def; | |
95 | ||
96 | case CALL: | |
97 | tree->degree = 10; | |
98 | break; | |
99 | ||
100 | case QUEST: | |
101 | case COLON: | |
102 | tree->degree = max(d1, d2); | |
103 | break; | |
104 | ||
105 | case MINUS: | |
106 | if (t = isconstant(tree->tr2)) { | |
107 | tree->op = PLUS; | |
108 | if (t->type==DOUBLE) | |
109 | /* PDP-11 FP representation */ | |
110 | t->value =^ 0100000; | |
111 | else | |
112 | t->value = -t->value; | |
113 | goto acomm; | |
114 | } | |
115 | goto def; | |
116 | ||
117 | case DIVIDE: | |
118 | case ASDIV: | |
119 | case ASTIMES: | |
120 | if (tree->tr2->op==CON && tree->tr2->value==1) | |
121 | return(tree->tr1); | |
122 | if (ispow2(tree) == 0) { | |
123 | ||
124 | case MOD: | |
125 | case ASMOD: | |
126 | d1 =+ 2; | |
127 | d2 =+ 2; | |
128 | } | |
129 | if (tree->type==LONG) | |
130 | return(hardlongs(tree)); | |
131 | goto constant; | |
132 | ||
133 | case LSHIFT: | |
134 | case RSHIFT: | |
135 | case ASRSH: | |
136 | case ASLSH: | |
137 | if (tree->tr2->op==CON && tree->tr2->value==0) | |
138 | return(tree->tr1); | |
139 | /* | |
140 | * PDP-11 special: turn right shifts into negative | |
141 | * left shifts | |
142 | */ | |
143 | if (op==LSHIFT||op==ASLSH) | |
144 | goto constant; | |
145 | if (tree->tr2->op==CON && tree->tr2->value==1) | |
146 | goto constant; | |
147 | op =+ (LSHIFT-RSHIFT); | |
148 | tree->op = op; | |
149 | tree->tr2 = block(1, NEG, tree->type, 0, tree->tr2); | |
150 | goto again; | |
151 | ||
152 | constant: | |
153 | if (tree->tr1->op==CON && tree->tr2->op==CON) { | |
154 | const(op, &tree->tr1->value, tree->tr2->value); | |
155 | return(tree->tr1); | |
156 | } | |
157 | ||
158 | ||
159 | def: | |
160 | default: | |
161 | tree->degree = d1==d2? d1+islong(tree->type): max(d1, d2); | |
162 | break; | |
163 | } | |
164 | return(tree); | |
165 | } | |
166 | ||
167 | unoptim(atree) | |
168 | struct tnode *atree; | |
169 | { | |
170 | register struct tnode *subtre, *tree; | |
171 | register int *p; | |
172 | double static fv; | |
173 | struct { int integer; }; | |
174 | ||
175 | if ((tree=atree)==0) | |
176 | return(0); | |
177 | if (tree->op==CBRANCH) { | |
178 | tree->btree = optim(tree->btree); | |
179 | return(tree); | |
180 | } | |
181 | subtre = tree->tr1 = optim(tree->tr1); | |
182 | switch (tree->op) { | |
183 | ||
184 | case FSEL: | |
185 | tree->tr1 = block(2, RSHIFT, INT, 0, subtre, | |
186 | block(1, CON, INT, 0, tree->bitoffs)); | |
187 | tree->op = AND; | |
188 | tree->type = INT; | |
189 | tree->tr2 = block(1, CON, INT, 0, (1<<tree->flen)-1); | |
190 | return(optim(tree)); | |
191 | ||
192 | case AMPER: | |
193 | if (subtre->op==STAR) | |
194 | return(subtre->tr1); | |
195 | if (subtre->op==NAME && subtre->class == OFFS) { | |
196 | p = block(2, PLUS, tree->type, 1, subtre, tree); | |
197 | subtre->type = tree->type; | |
198 | tree->op = CON; | |
199 | tree->type = INT; | |
200 | tree->degree = 0; | |
201 | tree->value = subtre->offset; | |
202 | subtre->class = REG; | |
203 | subtre->nloc = subtre->regno; | |
204 | subtre->offset = 0; | |
205 | return(p); | |
206 | } | |
207 | break; | |
208 | ||
209 | case STAR: | |
210 | if (subtre->op==AMPER) | |
211 | return(subtre->tr1); | |
212 | if (subtre->op==NAME && subtre->class==REG) { | |
213 | subtre->type = tree->type; | |
214 | subtre->class = OFFS; | |
215 | subtre->regno = subtre->nloc; | |
216 | return(subtre); | |
217 | } | |
218 | p = subtre->tr1; | |
219 | if ((subtre->op==INCAFT||subtre->op==DECBEF)&&tree->type!=LONG | |
220 | && p->op==NAME && p->class==REG && p->type==subtre->type) { | |
221 | p->type = tree->type; | |
222 | p->op = subtre->op==INCAFT? AUTOI: AUTOD; | |
223 | return(p); | |
224 | } | |
225 | if (subtre->op==PLUS && p->op==NAME && p->class==REG) { | |
226 | if (subtre->tr2->op==CON) { | |
227 | p->offset =+ subtre->tr2->value; | |
228 | p->class = OFFS; | |
229 | p->type = tree->type; | |
230 | p->regno = p->nloc; | |
231 | return(p); | |
232 | } | |
233 | if (subtre->tr2->op==AMPER) { | |
234 | subtre = subtre->tr2->tr1; | |
235 | subtre->class =+ XOFFS-EXTERN; | |
236 | subtre->regno = p->nloc; | |
237 | subtre->type = tree->type; | |
238 | return(subtre); | |
239 | } | |
240 | } | |
241 | break; | |
242 | case EXCLA: | |
243 | if ((opdope[subtre->op]&RELAT)==0) | |
244 | break; | |
245 | tree = subtre; | |
246 | tree->op = notrel[tree->op-EQUAL]; | |
247 | break; | |
248 | ||
249 | case NEG: | |
250 | case COMPL: | |
251 | if (tree->type==CHAR) | |
252 | tree->type = INT; | |
253 | if (tree->op == subtre->op) | |
254 | return(subtre->tr1); | |
255 | if (subtre->op==ITOL) { | |
256 | subtre->op = tree->op; | |
257 | subtre->type = INT; | |
258 | tree->op = ITOL; | |
259 | } | |
260 | } | |
261 | if (subtre->op == CON) switch(tree->op) { | |
262 | ||
263 | case NEG: | |
264 | subtre->value = -subtre->value; | |
265 | return(subtre); | |
266 | ||
267 | case COMPL: | |
268 | subtre->value = ~subtre->value; | |
269 | return(subtre); | |
270 | ||
271 | case ITOF: | |
272 | fv = subtre->value; | |
273 | p = &fv; | |
274 | p++; | |
275 | if (*p++==0 && *p++==0 && *p++==0) { | |
276 | subtre->type = DOUBLE; | |
277 | subtre->value = fv.integer; | |
278 | subtre->op = SFCON; | |
279 | return(subtre); | |
280 | } | |
281 | break; | |
282 | } | |
283 | tree->degree = max(islong(tree->type), degree(subtre)); | |
284 | return(tree); | |
285 | } | |
286 | ||
287 | struct acl { | |
288 | int nextl; | |
289 | int nextn; | |
290 | struct tnode *nlist[20]; | |
291 | struct tnode *llist[21]; | |
292 | }; | |
293 | ||
294 | acommute(atree) | |
295 | { | |
296 | struct acl acl; | |
297 | int d, i, op, flt; | |
298 | register struct tnode *t1, **t2, *tree; | |
299 | struct tnode *t; | |
300 | ||
301 | acl.nextl = 0; | |
302 | acl.nextn = 0; | |
303 | tree = atree; | |
304 | op = tree->op; | |
305 | flt = isfloat(tree); | |
306 | insert(op, tree, &acl); | |
307 | acl.nextl--; | |
308 | t2 = &acl.llist[acl.nextl]; | |
309 | if (!flt) { | |
310 | /* put constants together */ | |
311 | for (i=acl.nextl;i>0&&t2[0]->op==CON&&t2[-1]->op==CON;i--) { | |
312 | acl.nextl--; | |
313 | t2--; | |
314 | const(op, &t2[0]->value, t2[1]->value); | |
315 | } | |
316 | } | |
317 | if (op==PLUS || op==OR) { | |
318 | /* toss out "+0" */ | |
319 | if (acl.nextl>0 && (t1 = isconstant(*t2)) && t1->value==0) { | |
320 | acl.nextl--; | |
321 | t2--; | |
322 | } | |
323 | if (acl.nextl <= 0) | |
324 | return(*t2); | |
325 | /* subsume constant in "&x+c" */ | |
326 | if (op==PLUS && t2[0]->op==CON && t2[-1]->op==AMPER) { | |
327 | t2--; | |
328 | t2[0]->tr1->offset =+ t2[1]->value; | |
329 | acl.nextl--; | |
330 | } | |
331 | } else if (op==TIMES || op==AND) { | |
332 | t1 = acl.llist[acl.nextl]; | |
333 | if (t1->op==CON) { | |
334 | if (t1->value==0) | |
335 | return(t1); | |
336 | if (op==TIMES && t1->value==1 && acl.nextl>0) | |
337 | if (--acl.nextl <= 0) | |
338 | return(acl.llist[0]); | |
339 | } | |
340 | } | |
341 | if (op==PLUS && !flt) | |
342 | distrib(&acl); | |
343 | tree = *(t2 = &acl.llist[0]); | |
344 | d = max(degree(tree), islong(tree->type)); | |
345 | if (op==TIMES && !flt) | |
346 | d++; | |
347 | for (i=0; i<acl.nextl; i++) { | |
348 | t1 = acl.nlist[i]; | |
349 | t1->tr2 = t = *++t2; | |
350 | t1->degree = d = d==degree(t)? d+islong(t1->type): max(d, degree(t)); | |
351 | t1->tr1 = tree; | |
352 | tree = t1; | |
353 | if (tree->type==LONG) { | |
354 | if (tree->op==TIMES) | |
355 | tree = hardlongs(tree); | |
356 | else if (tree->op==PLUS && (t = isconstant(tree->tr1)) | |
357 | && t->value < 0) { | |
358 | tree->op = MINUS; | |
359 | t->value = - t->value; | |
360 | t = tree->tr1; | |
361 | tree->tr1 = tree->tr2; | |
362 | tree->tr2 = t; | |
363 | } | |
364 | } | |
365 | } | |
366 | if (tree->op==TIMES && ispow2(tree)) | |
367 | tree->degree = max(degree(tree->tr1), islong(tree->type)); | |
368 | return(tree); | |
369 | } | |
370 | ||
371 | distrib(list) | |
372 | struct acl *list; | |
373 | { | |
374 | /* | |
375 | * Find a list member of the form c1c2*x such | |
376 | * that c1c2 divides no other such constant, is divided by | |
377 | * at least one other (say in the form c1*y), and which has | |
378 | * fewest divisors. Reduce this pair to c1*(y+c2*x) | |
379 | * and iterate until no reductions occur. | |
380 | */ | |
381 | register struct tnode **p1, **p2; | |
382 | struct tnode *t; | |
383 | int ndmaj, ndmin; | |
384 | struct tnode **dividend, **divisor; | |
385 | struct tnode **maxnod, **mindiv; | |
386 | ||
387 | loop: | |
388 | maxnod = &list->llist[list->nextl]; | |
389 | ndmaj = 1000; | |
390 | dividend = 0; | |
391 | for (p1 = list->llist; p1 <= maxnod; p1++) { | |
392 | if ((*p1)->op!=TIMES || (*p1)->tr2->op!=CON) | |
393 | continue; | |
394 | ndmin = 0; | |
395 | for (p2 = list->llist; p2 <= maxnod; p2++) { | |
396 | if (p1==p2 || (*p2)->op!=TIMES || (*p2)->tr2->op!=CON) | |
397 | continue; | |
398 | if ((*p1)->tr2->value == (*p2)->tr2->value) { | |
399 | (*p2)->tr2 = (*p1)->tr1; | |
400 | (*p2)->op = PLUS; | |
401 | (*p1)->tr1 = (*p2); | |
402 | *p1 = optim(*p1); | |
403 | squash(p2, maxnod); | |
404 | list->nextl--; | |
405 | goto loop; | |
406 | } | |
407 | if (((*p2)->tr2->value % (*p1)->tr2->value) == 0) | |
408 | goto contmaj; | |
409 | if (((*p1)->tr2->value % (*p2)->tr2->value) == 0) { | |
410 | ndmin++; | |
411 | mindiv = p2; | |
412 | } | |
413 | } | |
414 | if (ndmin > 0 && ndmin < ndmaj) { | |
415 | ndmaj = ndmin; | |
416 | dividend = p1; | |
417 | divisor = mindiv; | |
418 | } | |
419 | contmaj:; | |
420 | } | |
421 | if (dividend==0) | |
422 | return; | |
423 | t = list->nlist[--list->nextn]; | |
424 | p1 = dividend; | |
425 | p2 = divisor; | |
426 | t->op = PLUS; | |
427 | t->type = (*p1)->type; | |
428 | t->tr1 = (*p1); | |
429 | t->tr2 = (*p2)->tr1; | |
430 | (*p1)->tr2->value =/ (*p2)->tr2->value; | |
431 | (*p2)->tr1 = t; | |
432 | t = optim(*p2); | |
433 | if (p1 < p2) { | |
434 | *p1 = t; | |
435 | squash(p2, maxnod); | |
436 | } else { | |
437 | *p2 = t; | |
438 | squash(p1, maxnod); | |
439 | } | |
440 | list->nextl--; | |
441 | goto loop; | |
442 | } | |
443 | ||
444 | squash(p, maxp) | |
445 | struct tnode **p, **maxp; | |
446 | { | |
447 | register struct tnode **np; | |
448 | ||
449 | for (np = p; np < maxp; np++) | |
450 | *np = *(np+1); | |
451 | } | |
452 | ||
453 | const(op, vp, av) | |
454 | int *vp; | |
455 | { | |
456 | register int v; | |
457 | ||
458 | v = av; | |
459 | switch (op) { | |
460 | ||
461 | case PLUS: | |
462 | *vp =+ v; | |
463 | return; | |
464 | ||
465 | case TIMES: | |
466 | *vp =* v; | |
467 | return; | |
468 | ||
469 | case AND: | |
470 | *vp =& v; | |
471 | return; | |
472 | ||
473 | case OR: | |
474 | *vp =| v; | |
475 | return; | |
476 | ||
477 | case EXOR: | |
478 | *vp =^ v; | |
479 | return; | |
480 | ||
481 | case DIVIDE: | |
482 | case MOD: | |
483 | if (v==0) | |
484 | error("Divide check"); | |
485 | else | |
486 | if (op==DIVIDE) | |
487 | *vp =/ v; | |
488 | else | |
489 | *vp =% v; | |
490 | return; | |
491 | ||
492 | case RSHIFT: | |
493 | *vp =>> v; | |
494 | return; | |
495 | ||
496 | case LSHIFT: | |
497 | *vp =<< v; | |
498 | return; | |
499 | ||
500 | case NAND: | |
501 | *vp =& ~ v; | |
502 | return; | |
503 | } | |
504 | error("C error: const"); | |
505 | } | |
506 | ||
507 | insert(op, atree, alist) | |
508 | struct acl *alist; | |
509 | { | |
510 | register d; | |
511 | register struct acl *list; | |
512 | register struct tnode *tree; | |
513 | int d1, i; | |
514 | struct tnode *t; | |
515 | ||
516 | tree = atree; | |
517 | list = alist; | |
518 | if (tree->op == op) { | |
519 | ins: list->nlist[list->nextn++] = tree; | |
520 | insert(op, tree->tr1, list); | |
521 | insert(op, tree->tr2, list); | |
522 | return; | |
523 | } | |
524 | tree = optim(tree); | |
525 | if (tree->op == op) | |
526 | goto ins; | |
527 | if (!isfloat(tree)) { | |
528 | /* c1*(x+c2) -> c1*x+c1*c2 */ | |
529 | if ((tree->op==TIMES||tree->op==LSHIFT) | |
530 | && tree->tr2->op==CON && tree->tr2->value>0 | |
531 | && tree->tr1->op==PLUS && tree->tr1->tr2->op==CON) { | |
532 | d = tree->tr2->value; | |
533 | if (tree->op==TIMES) | |
534 | tree->tr2->value =* tree->tr1->tr2->value; | |
535 | else | |
536 | tree->tr2->value = tree->tr1->tr2->value << d; | |
537 | tree->tr1->tr2->value = d; | |
538 | tree->tr1->op = tree->op; | |
539 | tree->op = PLUS; | |
540 | if (op==PLUS) | |
541 | goto ins; | |
542 | } | |
543 | } | |
544 | d = degree(tree); | |
545 | for (i=0; i<list->nextl; i++) { | |
546 | if ((d1=degree(list->llist[i]))<d) { | |
547 | t = list->llist[i]; | |
548 | list->llist[i] = tree; | |
549 | tree = t; | |
550 | d = d1; | |
551 | } | |
552 | } | |
553 | list->llist[list->nextl++] = tree; | |
554 | } | |
555 | ||
556 | block(an, args) | |
557 | { | |
558 | register int *p; | |
559 | int *oldp; | |
560 | register *argp, n; | |
561 | ||
562 | oldp = p = spacep; | |
563 | n = an+3; | |
564 | argp = &args; | |
565 | do | |
566 | *p++ = *argp++; | |
567 | while (--n); | |
568 | if (p >= &treespace[ossiz]) { | |
569 | error("Exp. ov. pass 2"); | |
570 | exit(1); | |
571 | } | |
572 | spacep = p; | |
573 | return(oldp); | |
574 | } | |
575 | ||
576 | islong(t) | |
577 | { | |
578 | if (t==LONG) | |
579 | return(2); | |
580 | return(1); | |
581 | } | |
582 | ||
583 | isconstant(at) | |
584 | struct tnode *at; | |
585 | { | |
586 | register struct tnode *t; | |
587 | ||
588 | t = at; | |
589 | if (t->op==CON || t->op==SFCON) | |
590 | return(t); | |
591 | if (t->op==ITOL && t->tr1->op==CON) | |
592 | return(t->tr1); | |
593 | return(0); | |
594 | } | |
595 | ||
596 | hardlongs(at) | |
597 | struct tnode *at; | |
598 | { | |
599 | register struct tnode *t; | |
600 | ||
601 | t = at; | |
602 | switch(t->op) { | |
603 | ||
604 | case TIMES: | |
605 | case DIVIDE: | |
606 | case MOD: | |
607 | t->op =+ LTIMES-TIMES; | |
608 | break; | |
609 | ||
610 | case ASTIMES: | |
611 | case ASDIV: | |
612 | case ASMOD: | |
613 | t->op =+ LASTIMES-ASTIMES; | |
614 | t->tr1 = block(1, AMPER, LONG+PTR, 0, t->tr1); | |
615 | break; | |
616 | ||
617 | default: | |
618 | return(t); | |
619 | } | |
620 | return(optim(t)); | |
621 | } |