projects / unix-history / blame
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Research V7 development
[unix-history] / .ref-Research-V6 / usr / source / c / c12.c
CommitLineData
cac4f7ea
DR		 1#
2/*
3 * C compiler part 2 -- expression optimizer
4 *
5 */
6
7#include "c1h.c"
8
9optim(atree)
10struct 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
167unoptim(atree)
168struct 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
287struct acl {
288 int nextl;
289 int nextn;
290 struct tnode *nlist[20];
291 struct tnode *llist[21];
292};
293
294acommute(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
371distrib(list)
372struct 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
444squash(p, maxp)
445struct tnode **p, **maxp;
446{
447 register struct tnode **np;
448
449 for (np = p; np < maxp; np++)
450 *np = *(np+1);
451}
452
453const(op, vp, av)
454int *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
507insert(op, atree, alist)
508struct 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
556block(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
576islong(t)
577{
578 if (t==LONG)
579 return(2);
580 return(1);
581}
582
583isconstant(at)
584struct 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
596hardlongs(at)
597struct 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}
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.