![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to opt.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / pico|
Return to opt.c CVS log | Up to [Research Unix] / researchv10no / cmd / pico |
1.1 root 1: #include "pico.h"
2:
3: long eval();
4: Node* abase();
5: Node *new();
6: #define ARITH 1
7: #define BOOL 0
8: #define Z ((Node *)0)
9: #define OK(x) (x==0)
10: #define EQ(x,y) ((x)==(y))
11: #define IS(x,y) EQ((x)->type,(y))
12: #define OSIZE 50
13:
14: rewrite(n, context)
15: Node *n;
16: {
17: long v;
18:
19: if(n == Z)
20: return;
21: if(isconst(n)) {
22: if(!IS(n,CONST) && !IS(n,CONSTB))
23: mkconst(n, eval(n, context));
24: return;
25: }
26: switch(n->type)
27: {
28: case LABL:
29: rewrite(n->left, context);
30: return;
31:
32: case GOTO:
33: case VAR:
34: case OARG:
35: case REG:
36: return;
37:
38: case CONDI:
39: if(isconst(n->other)) {
40: v = eval(n->other, BOOL);
41: if(v) {
42: rewrite(n->left, context);
43: *n = *n->left;
44: return;
45: }
46: rewrite(n->right, context);
47: *n = *n->right;
48: return;
49: }
50: rewrite(n->other, BOOL);
51: iknown(n->other, n->left, 1);
52: rewrite(n->left, context);
53: if(n->right != Z) {
54: iknown(n->other, n->right, 0);
55: rewrite(n->right, context);
56: if(compr(n->left, n->right) == 0)
57: *n = *n->right;
58: }
59: return;
60:
61: case DEREFB:
62: rewrite(n->left, ARITH);
63: rewrite(n->right, ARITH);
64: if(n->left->type != VAR)
65: return;
66: if(IS(n->right,CONST)) {
67: n->left->arg += n->right->arg;
68: n->right = Z;
69: return;
70: }
71: if(IS(n->right,OADD))
72: if(IS(n->right->right,CONST)) {
73: n->left->arg += n->right->right->arg;
74: n->right = n->right->left;
75: return;
76: }
77: return;
78:
79: case DEREFS:
80: rewrite(n->left, ARITH);
81: rewrite(n->right, ARITH);
82: if(n->left->type != VAR)
83: return;
84: if(IS(n->right,CONST)) {
85: n->left->arg += 2*n->right->arg;
86: n->right = Z;
87: return;
88: }
89: if(IS(n->right,OADD))
90: if(IS(n->right->right,CONST)) {
91: n->left->arg += 2*n->right->right->arg;
92: n->right = n->right->left;
93: return;
94: }
95: return;
96:
97: case DEREFL:
98: rewrite(n->left, ARITH);
99: rewrite(n->right, ARITH);
100: if(n->left->type != VAR)
101: return;
102: if(IS(n->right,CONST)) {
103: n->left->arg += 4*n->right->arg;
104: n->right = Z;
105: return;
106: }
107: if(IS(n->right,OADD))
108: if(IS(n->right->right,CONST)) {
109: n->left->arg += 4*n->right->right->arg;
110: n->right = n->right->left;
111: return;
112: }
113: return;
114:
115: case OADD:
116: case OSUB:
117: case OISUB:
118: case OMINUS:
119: acan(n);
120: return;
121:
122: case OMUL:
123: scan(n, 1L);
124: return;
125:
126: case ODIV:
127: rewrite(n->left, ARITH);
128: rewrite(n->right, ARITH);
129: if(IS(n->right,CONST)) {
130: v = n->right->arg;
131: if(v == 1)
132: *n = *n->left;
133: }
134: return;
135:
136: case OIDIV:
137: rewrite(n->left, ARITH);
138: rewrite(n->right, ARITH);
139: if(IS(n->left,CONST)) {
140: v = n->left->arg;
141: if(v == 1)
142: *n = *n->right;
143: }
144: return;
145:
146: case OPOW:
147: case OBIC:
148: case OLSH:
149: rewrite(n->left, ARITH);
150: rewrite(n->right, ARITH);
151: return;
152:
153: case ORETURN:
154: rewrite(n->left, ARITH);
155: return;
156:
157: case OAND:
158: scan(n, -1L);
159: if(IS(n, OAND))
160: if(context == ARITH)
161: fixbic(n);
162: return;
163:
164: case OOR:
165: case OXOR:
166: scan(n, 0L);
167: return;
168:
169: case ONEG:
170: rewrite(n->left, context);
171: return;
172:
173: case OCOMMA:
174: case ACOMMA:
175: rewrite(n->left, ARITH);
176: rewrite(n->right, context);
177: return;
178:
179: case OCALL:
180: case CCALL:
181: rewrite(n->left, ARITH);
182: return;
183:
184: case OASS:
185: rewrite(n->left, context);
186: rewrite(n->right, context);
187: return;
188:
189: case COMP:
190: rewrite(n->left, ARITH);
191: return;
192:
193: case OGT:
194: case OLT:
195: case OLE:
196: case OGE:
197: case ONE:
198: case OEQ:
199: rewrite(n->left, ARITH);
200: rewrite(n->right, ARITH);
201: if(n->right && IS(n->right,CONST) && n->right->arg == 0) {
202: n->right = Z;
203: return;
204: }
205: if(n->left && IS(n->left,CONST) && n->left->arg == 0) {
206: n->left = n->right;
207: n->right = Z;
208: n->type = comop(n->type);
209: return;
210: }
211: return;
212:
213: case OOROR:
214: rewrite(n->left, BOOL);
215: rewrite(n->right, BOOL);
216: if(IS(n->left,CONST)) {
217: *n = *n->right;
218: return;
219: }
220: if(IS(n->right,CONST)) {
221: if(!eval(n->right, BOOL))
222: *n = *n->right;
223: return;
224: }
225: iknown(n->left, n->right, 0);
226: return;
227:
228: case OANDAND:
229: rewrite(n->left, BOOL);
230: rewrite(n->right, BOOL);
231: if(IS(n->left,CONST)) {
232: *n = *n->right;
233: return;
234: }
235: if(IS(n->right,CONST)) {
236: if(eval(n->right, BOOL))
237: *n = *n->right;
238: return;
239: }
240: iknown(n->left, n->right, 1);
241: return;
242:
243: case ONOT:
244: rewrite(n->left, BOOL);
245: return;
246: }
247: printf("type = %d\n", n->type);
248: }
249:
250: comop(o)
251: {
252:
253: switch(o) {
254:
255: case OLT: o = OGE; break;
256: case OLE: o = OGT; break;
257: case OGT: o = OLE; break;
258: case OGE: o = OLT; break;
259: }
260: return(o);
261: }
262:
263: fixbic(n)
264: Node *n;
265: {
266:
267: if(!IS(n->right,CONST))
268: return;
269: n->right->arg = ~n->right->arg;
270: n->type = OBIC;
271: }
272:
273: iknown(x, n, f)
274: Node *n, *x;
275: {
276:
277: if (n == Z)
278: return;
279:
280: known(x, n, f);
281: switch(x->type) {
282:
283: case ONOT:
284: iknown(x->left, n, !f);
285: break;
286:
287: case OAND:
288: if(f) {
289: if(isconst(x->left))
290: iknown(x->right, n, 1);
291: if(isconst(x->right))
292: iknown(x->left, n, 1);
293: }
294: break;
295:
296: case OOR:
297: if(!f) {
298: if(isconst(x->left))
299: iknown(x->right, n, 0);
300: if(isconst(x->right))
301: iknown(x->left, n, 0);
302: }
303: break;
304: }
305: }
306:
307: known(x, n, f)
308: Node *n, *x;
309: {
310:
311: if(compr(x, n) == 0) {
312: if(f == 0) {
313: mkconst(n, 0L);
314: return;
315: }
316: }
317: switch(n->type) {
318:
319: case CONDI:
320: known(x, n->other, f);
321: if(compr(x, n->other) == 0) {
322: if(f)
323: *n = *n->left;
324: else
325: *n = *n->right;
326: known(x, n, f);
327: return;
328: }
329: break;
330:
331: case OANDAND:
332: if(compr(x, n->left) == 0) {
333: if(f)
334: mkconst(n, 1L);
335: else
336: *n = *n->right;
337: known(x, n, f);
338: return;
339: }
340: if(compr(x, n->right) == 0) {
341: if(f)
342: mkconst(n->right, 1L);
343: else
344: *n = *n->left;
345: known(x, n, f);
346: return;
347: }
348: break;
349:
350: case OOROR:
351: if(compr(x, n->left) == 0) {
352: if(f)
353: *n = *n->right;
354: else
355: mkconst(n, 0L);
356: known(x, n, f);
357: return;
358: }
359: if(compr(x, n->right) == 0) {
360: if(f)
361: *n = *n->left;
362: else
363: mkconst(n->right, 0L);
364: known(x, n, f);
365: return;
366: }
367: break;
368: }
369: if(n->right)
370: known(x, n->right, f);
371: if(n->left)
372: known(x, n->left, f);
373: }
374:
375: mkconst(n, v)
376: Node *n;
377: long v;
378: {
379:
380: n->type = CONST;
381: n->other = Z;
382: n->left = Z;
383: n->right = Z;
384: n->arg = v;
385: }
386:
387:
388: isconst(n)
389: Node *n;
390: {
391:
392: if(n == Z)
393: return 0;
394: switch(n->type)
395: {
396:
397: case CONST:
398: case CONSTB:
399: return 1;
400:
401: case REG:
402: case VAR:
403: case OARG:
404: case DEREFB:
405: case DEREFS:
406: case DEREFL:
407: case OCALL:
408: case CCALL:
409: case OASS:
410: case GOTO:
411: case LABL:
412: case OCOMMA:
413: case ACOMMA:
414: case ORETURN:
415: return 0;
416:
417: case COMP:
418: for (n = n->left; n->type == ACOMMA; n = n->left)
419: if(!isconst(n->left))
420: return 0;
421: return isconst(n);
422:
423: case OANDAND:
424: if(isconst(n->left)) {
425: if(!eval(n->left, BOOL))
426: return 1;
427: return isconst(n->right);
428: }
429: return 0;
430:
431: case OOROR:
432: if(isconst(n->left)) {
433: if(eval(n->left, BOOL))
434: return 1;
435: return isconst(n->right);
436: }
437: return 0;
438:
439: case CONDI:
440: if(!isconst(n->other))
441: return 0;
442: if(eval(n->other, BOOL))
443: return isconst(n->left);
444: return isconst(n->right);
445: }
446: if(n->left)
447: if(!isconst(n->left))
448: return 0;
449: if(n->right)
450: if(!isconst(n->right))
451: return 0;
452: return 1;
453: }
454:
455: struct O
456: {
457: struct l
458: {
459: Node *n;
460: long f;
461: } l[OSIZE];
462: Node *free;
463: int count;
464: } O;
465:
466: cancmp1(p1, p2)
467: struct l *p1, *p2;
468: {
469:
470: return compr(p1->n, p2->n);
471: }
472:
473: scan1(n, o)
474: Node *n;
475: {
476:
477: if(IS(n,o)) {
478: scan1(n->left, o);
479: scan1(n->right, o);
480: return;
481: }
482: rewrite(n, ARITH);
483: }
484:
485: scan2(n, o)
486: Node *n;
487: {
488:
489: if(IS(n,o)) {
490: scan2(n->left, o);
491: scan2(n->right, o);
492: n->type = o;
493: n->left = O.free;
494: n->right = Z;
495: n->arg = 0;
496: O.free = n;
497: return;
498: }
499: O.l[O.count].n = n;
500: O.count++;
501: if(O.count >= OSIZE)
502: yyerror("OSIZE too small");
503: }
504:
505: scan(n, z)
506: Node *n;
507: long z;
508: {
509: Node t;
510: int i, j, o;
511:
512: o = n->type;
513: scan1(n, o);
514: O.count = 0;
515: O.free = Z;
516: scan2(n, o);
517: qsort(O.l, O.count, sizeof O.l[0], cancmp1);
518:
519: j = 0;
520: for(i=0; i<O.count; i++) {
521: if(j)
522: if(IS(O.l[i].n,CONST)) {
523: t.type = o;
524: t.left = O.l[i].n;
525: t.right = O.l[j-1].n;
526: mkconst(O.l[i].n, eval(&t, ARITH));
527: O.l[j-1].n = O.l[i].n;
528: continue;
529: }
530: if(j)
531: if(compr(O.l[j-1].n, O.l[i].n) == 0) {
532: /* x^x => 0 */
533: if(o == OXOR) {
534: j--;
535: continue;
536: }
537: /* x&x => x */
538: /* x|x => x */
539: if(o == OAND || o == OOR)
540: continue;
541: }
542: O.l[j].n = O.l[i].n;
543: if(IS(O.l[j].n,CONST))
544: if(O.l[j].n->arg == z)
545: continue;
546: j++;
547: }
548: O.count = j;
549: if(n != O.free)
550: yyerror("scan smells");
551: if(O.count == 0) {
552: mkconst(n, z);
553: return;
554: }
555: if(O.count == 1) {
556: *n = *O.l[0].n;
557: return;
558: }
559: for(i=0; i<O.count-2; i++) {
560: O.free->right = O.l[i].n;
561: O.free = O.free->left;
562: }
563: O.free->right = O.l[i].n;
564: O.free->left = O.l[i+1].n;
565: }
566:
567: acan1(n)
568: Node *n;
569: {
570: register t;
571:
572: t = n->type;
573: if(EQ(t,OADD)||EQ(t,OSUB)||EQ(t,OMINUS)||EQ(t,OISUB)) {
574: acan1(n->left);
575: if(n->right)
576: acan1(n->right);
577: return;
578: }
579: if (t == OISUB) yyerror("hit bug in optimizer (loop)");
580: rewrite(n, ARITH);
581: }
582:
583: acan2(n, f)
584: Node *n;
585: long f;
586: {
587: register t;
588:
589: t = n->type;
590: if(EQ(t,OADD)) {
591: acan2(n->left, f);
592: acan2(n->right, f);
593: goto out;
594: }
595: if(EQ(t,OSUB)) {
596: acan2(n->left, f);
597: acan2(n->right, -f);
598: goto out;
599: }
600: if(EQ(t,OISUB)) {
601: acan2(n->left, -f);
602: acan2(n->right, f);
603: goto out;
604: }
605: if(EQ(t,OMINUS)) {
606: acan2(n->left, -f);
607: goto out;
608: }
609: if(EQ(t,OMUL))
610: if(IS(n->right,CONST)) {
611: f *= n->right->arg;
612: acan2(n->left, f);
613: goto out;
614: }
615: if(f != 1 && IS(n,CONST)) {
616: mkconst(n, f*n->arg);
617: f = 1;
618: }
619: O.l[O.count].n = n;
620: O.l[O.count].f = f;
621: O.count++;
622: if(O.count >= OSIZE)
623: yyerror("OSIZE too small");
624: return;
625:
626: out:
627: n->type = OADD;
628: n->left = O.free;
629: n->right = Z;
630: n->arg = 0;
631: O.free = n;
632: }
633:
634: acan3()
635: {
636: int i, j;
637: long nator, dator;
638: Node *t;
639:
640: if(IS(O.l[0].n,CONST))
641: if(O.l[0].n->arg < 0) {
642: O.l[0].n->arg = -O.l[0].n->arg;
643: O.l[0].f = -O.l[0].f;
644: }
645: for(i=0; i<O.count; i++) {
646: if(IS(O.l[i].n,CONST))
647: continue;
648: dator = O.l[i].f;
649: if(dator < 0)
650: dator = -dator;
651: if(dator <= 1)
652: continue;
653: for(j=0; j<O.count; j++) {
654: if(i == j)
655: continue;
656: nator = O.l[j].f;
657: if(IS(O.l[j].n,CONST))
658: nator = O.l[j].n->arg;
659: if(nator < 0)
660: nator = -nator;
661: if(nator%dator)
662: continue;
663: if(IS(O.l[j].n,CONST)) {
664: O.l[j].n->arg = nator/dator;
665: t = O.l[j].n;
666: } else
667: if(dator == nator) {
668: t = O.l[j].n;
669: } else {
670: t = new(CONST, Z, Z, nator/dator);
671: t = new(OMUL, O.l[j].n, t, 0L);
672: }
673: if(O.l[j].f < 0)
674: t = new(OSUB, O.l[i].n, t, 0L);
675: else
676: t = new(OADD, O.l[i].n, t, 0L);
677: O.l[i].n = t;
678: O.l[j].f = 0;
679: }
680: }
681: j = 0;
682: for(i=0; i<O.count; i++) {
683: if(O.l[i].f == 0)
684: continue;
685: O.l[j].n = O.l[i].n;
686: O.l[j].f = O.l[i].f;
687: j++;
688: }
689: O.count = j;
690: for(i=O.count-1; i>=0; i--) {
691: if(O.l[i].f < 0)
692: continue;
693: }
694: }
695:
696: Node *
697: atemp(i)
698: {
699: Node *t;
700: int f;
701:
702: f = O.l[i].f;
703: if(f < 0)
704: f = -f;
705: if(f != 1) {
706: t = new(CONST, Z, Z, f);
707: if(f)
708: t = new(OMUL, O.l[i].n, t, 0L);
709: return t;
710: }
711: return O.l[i].n;
712: }
713:
714: acan(n)
715: Node *n;
716: {
717: Node t;
718: int i, j;
719:
720: acan1(n);
721: O.count = 0;
722: O.free = Z;
723: acan2(n, 1L);
724: qsort(O.l, O.count, sizeof O.l[0], cancmp1);
725:
726: j = 0;
727: for(i=0; i<O.count; i++) {
728: if(j)
729: if(IS(O.l[i].n,CONST)) {
730: t.type = OADD;
731: t.left = O.l[i].n;
732: t.right = O.l[j-1].n;
733: mkconst(O.l[i].n, eval(&t, ARITH));
734: O.l[j-1].n = O.l[i].n;
735: continue;
736: }
737: if(j)
738: if(compr(O.l[j-1].n, O.l[i].n) == 0) {
739: O.l[j-1].f += O.l[i].f;
740: if(O.l[j-1].f == 0)
741: j--;
742: continue;
743: }
744: O.l[j].n = O.l[i].n;
745: O.l[j].f = O.l[i].f;
746: if(IS(O.l[j].n,CONST))
747: if(O.l[j].n->arg == 0)
748: continue;
749: j++;
750: }
751: O.count = j;
752: acan3();
753: if(n != O.free)
754: yyerror("acan smells");
755: if(O.count == 0) {
756: mkconst(n, 0L);
757: return;
758: }
759: j = -1;
760: for(i=0; i<O.count; i++)
761: if(O.l[i].f >= 0)
762: j = i;
763: if(j < 0) {
764: if(IS(O.l[0].n,CONST)) {
765: O.l[0].n->arg = -O.l[0].n->arg;
766: O.l[0].f = -O.l[0].f;
767: j = 0;
768: } else {
769: O.free->type = OMINUS;
770: if(O.count == 1) {
771: O.free->left = atemp(0);
772: return;
773: }
774: O.free = O.free->left;
775: }
776: }
777: for(i=j+1; i<O.count; i++)
778: O.l[i].f = -O.l[i].f;
779: if(O.count == 1) {
780: *O.free = *atemp(0);
781: return;
782: }
783: for(i=0; i<O.count-2; i++) {
784: O.free->right = atemp(i);
785: if(O.l[i].f < 0)
786: O.free->type = OSUB;
787: else
788: if(i == j)
789: O.free->type = OISUB;
790: O.free = O.free->left;
791: }
792: O.free->right = atemp(i);
793: if(O.l[i].f < 0)
794: O.free->type = OSUB;
795: else
796: if(i == j)
797: O.free->type = OISUB;
798: O.free->left = atemp(i+1);
799: }
800:
801: compr(n1, n2)
802: Node *n1, *n2;
803: {
804: int v;
805:
806: v = n1->type - n2->type;
807: if(v) {
808: if(IS(n1,CONST))
809: return -1;
810: if(IS(n2,CONST))
811: return 1;
812: return v;
813: }
814: switch(n1->type)
815: {
816:
817: case VAR:
818: case CONST:
819: case REG:
820: case OARG:
821: v = n1->arg - n2->arg;
822: return v;
823:
824: case CONDI:
825: v = compr(n1->other, n2->other);
826: if(v)
827: return v;
828:
829: case OCALL:
830: case CCALL:
831: case LABL:
832: case GOTO:
833: return -1;
834: }
835: v = compr(n1->left, n2->left);
836: if(v)
837: return v;
838: if(n1->right)
839: return compr(n1->right, n2->right);
840: return 0;
841: }
842:
843: dlist()
844: {
845: int i;
846:
847: for(i=0; i<O.count; i++) {
848: printf("[%2d] ", i);
849: printf("%3d ", O.l[i].f);
850: prtree(O.l[i].n, 0, 5);
851: }
852: printf("\n");
853: }
854:
855: long
856: eval(n, context)
857: Node *n;
858: {
859: Node n1, n2;
860: long v;
861:
862:
863: if(context == BOOL) {
864: n1.type = ONOT;
865: n1.left = &n2;
866: n1.right = Z;
867: n1.other = Z;
868:
869: n2.type = ONOT;
870: n2.left = n;
871: n2.right = Z;
872: n2.other = Z;
873:
874: n = &n1;
875: }
876: gencode(n);
877: v = callit();
878: return v;
879: }
880:
881: callit()
882: {
883: register x, y, z;
884: extern program();
885:
886: x = y = z = 0;
887: asm(" jsb *_program ");
888: asm(" x: brb x+9 ");
889: x = program();
890: return(x);
891: }
892:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.