1442524f6Sralph #ifndef lint
2*61c78690Sdonn static char *sccsid ="@(#)optim.c 4.7 (Berkeley) 01/08/86";
3442524f6Sralph #endif lint
4442524f6Sralph
57dffd0ceSralph # include "pass1.h"
63c5bb8e1Sralph
73c5bb8e1Sralph # define SWAP(p,q) {sp=p; p=q; q=sp;}
83c5bb8e1Sralph # define RCON(p) (p->in.right->in.op==ICON)
93c5bb8e1Sralph # define RO(p) p->in.right->in.op
103c5bb8e1Sralph # define RV(p) p->in.right->tn.lval
113c5bb8e1Sralph # define LCON(p) (p->in.left->in.op==ICON)
123c5bb8e1Sralph # define LO(p) p->in.left->in.op
133c5bb8e1Sralph # define LV(p) p->in.left->tn.lval
143c5bb8e1Sralph
15a9d74daaSmckusick /* is p a constant without a name */
16a9d74daaSmckusick # define nncon(p) ((p)->in.op == ICON && (p)->tn.rval == NONAME)
17a9d74daaSmckusick
183c5bb8e1Sralph int oflag = 0;
193c5bb8e1Sralph
203c5bb8e1Sralph NODE *
fortarg(p)213c5bb8e1Sralph fortarg( p ) NODE *p; {
223c5bb8e1Sralph /* fortran function arguments */
233c5bb8e1Sralph
243c5bb8e1Sralph if( p->in.op == CM ){
253c5bb8e1Sralph p->in.left = fortarg( p->in.left );
263c5bb8e1Sralph p->in.right = fortarg( p->in.right );
273c5bb8e1Sralph return(p);
283c5bb8e1Sralph }
293c5bb8e1Sralph
303c5bb8e1Sralph while( ISPTR(p->in.type) ){
313c5bb8e1Sralph p = buildtree( UNARY MUL, p, NIL );
323c5bb8e1Sralph }
333c5bb8e1Sralph return( optim(p) );
343c5bb8e1Sralph }
353c5bb8e1Sralph
363c5bb8e1Sralph /* mapping relationals when the sides are reversed */
373c5bb8e1Sralph short revrel[] ={ EQ, NE, GE, GT, LE, LT, UGE, UGT, ULE, ULT };
383c5bb8e1Sralph NODE *
optim(p)393c5bb8e1Sralph optim(p) register NODE *p; {
403c5bb8e1Sralph /* local optimizations, most of which are probably machine independent */
413c5bb8e1Sralph
423c5bb8e1Sralph register o, ty;
433c5bb8e1Sralph NODE *sp;
443c5bb8e1Sralph int i;
453c5bb8e1Sralph TWORD t;
463c5bb8e1Sralph
473c5bb8e1Sralph if( (t=BTYPE(p->in.type))==ENUMTY || t==MOETY ) econvert(p);
483c5bb8e1Sralph if( oflag ) return(p);
493c5bb8e1Sralph ty = optype( o=p->in.op);
503c5bb8e1Sralph if( ty == LTYPE ) return(p);
513c5bb8e1Sralph
523c5bb8e1Sralph if( ty == BITYPE ) p->in.right = optim(p->in.right);
533c5bb8e1Sralph p->in.left = optim(p->in.left);
543c5bb8e1Sralph
553c5bb8e1Sralph /* collect constants */
563c5bb8e1Sralph
573c5bb8e1Sralph switch(o){
583c5bb8e1Sralph
593c5bb8e1Sralph case SCONV:
603c5bb8e1Sralph case PCONV:
613c5bb8e1Sralph return( clocal(p) );
623c5bb8e1Sralph
633c5bb8e1Sralph case FORTCALL:
643c5bb8e1Sralph p->in.right = fortarg( p->in.right );
653c5bb8e1Sralph break;
663c5bb8e1Sralph
673c5bb8e1Sralph case UNARY AND:
68b0b65fcdSralph if( LO(p) != NAME || !andable(p->in.left) ) return(p);
693c5bb8e1Sralph
703c5bb8e1Sralph LO(p) = ICON;
713c5bb8e1Sralph
723c5bb8e1Sralph setuleft:
733c5bb8e1Sralph /* paint over the type of the left hand side with the type of the top */
743c5bb8e1Sralph p->in.left->in.type = p->in.type;
753c5bb8e1Sralph p->in.left->fn.cdim = p->fn.cdim;
763c5bb8e1Sralph p->in.left->fn.csiz = p->fn.csiz;
773c5bb8e1Sralph p->in.op = FREE;
783c5bb8e1Sralph return( p->in.left );
793c5bb8e1Sralph
803c5bb8e1Sralph case UNARY MUL:
813c5bb8e1Sralph if( LO(p) != ICON ) break;
823c5bb8e1Sralph LO(p) = NAME;
833c5bb8e1Sralph goto setuleft;
843c5bb8e1Sralph
853c5bb8e1Sralph case MINUS:
863c5bb8e1Sralph if( !nncon(p->in.right) ) break;
873c5bb8e1Sralph RV(p) = -RV(p);
883c5bb8e1Sralph o = p->in.op = PLUS;
893c5bb8e1Sralph
903c5bb8e1Sralph case MUL:
913c5bb8e1Sralph case PLUS:
923c5bb8e1Sralph case AND:
933c5bb8e1Sralph case OR:
943c5bb8e1Sralph case ER:
953c5bb8e1Sralph /* commutative ops; for now, just collect constants */
963c5bb8e1Sralph /* someday, do it right */
973c5bb8e1Sralph if( nncon(p->in.left) || ( LCON(p) && !RCON(p) ) ) SWAP( p->in.left, p->in.right );
983c5bb8e1Sralph /* make ops tower to the left, not the right */
993c5bb8e1Sralph if( RO(p) == o ){
1003c5bb8e1Sralph NODE *t1, *t2, *t3;
1013c5bb8e1Sralph t1 = p->in.left;
1023c5bb8e1Sralph sp = p->in.right;
1033c5bb8e1Sralph t2 = sp->in.left;
1043c5bb8e1Sralph t3 = sp->in.right;
1053c5bb8e1Sralph /* now, put together again */
1063c5bb8e1Sralph p->in.left = sp;
1073c5bb8e1Sralph sp->in.left = t1;
1083c5bb8e1Sralph sp->in.right = t2;
1093c5bb8e1Sralph p->in.right = t3;
1103c5bb8e1Sralph }
1113c5bb8e1Sralph if(o == PLUS && LO(p) == MINUS && RCON(p) && RCON(p->in.left) &&
1123c5bb8e1Sralph conval(p->in.right, MINUS, p->in.left->in.right)){
1133c5bb8e1Sralph zapleft:
1143c5bb8e1Sralph RO(p->in.left) = FREE;
1153c5bb8e1Sralph LO(p) = FREE;
1163c5bb8e1Sralph p->in.left = p->in.left->in.left;
1173c5bb8e1Sralph }
118a9d74daaSmckusick if( RCON(p) && LO(p)==o && RCON(p->in.left) &&
119a9d74daaSmckusick conval( p->in.right, o, p->in.left->in.right ) ){
1203c5bb8e1Sralph goto zapleft;
1213c5bb8e1Sralph }
122a9d74daaSmckusick else if( LCON(p) && RCON(p) &&
123a9d74daaSmckusick conval( p->in.left, o, p->in.right ) ){
1243c5bb8e1Sralph zapright:
1253c5bb8e1Sralph RO(p) = FREE;
1263c5bb8e1Sralph p->in.left = makety( p->in.left, p->in.type, p->fn.cdim, p->fn.csiz );
1273c5bb8e1Sralph p->in.op = FREE;
1283c5bb8e1Sralph return( clocal( p->in.left ) );
1293c5bb8e1Sralph }
130a9d74daaSmckusick /* FALL THROUGH */
1313c5bb8e1Sralph
132a9d74daaSmckusick case ASG MUL:
133a9d74daaSmckusick /* change muls to adds or shifts */
1343c5bb8e1Sralph
135a9d74daaSmckusick if( (o == MUL || o == ASG MUL) &&
136a9d74daaSmckusick nncon(p->in.right) && (i=ispow2(RV(p)))>=0){
137a9d74daaSmckusick if( i == 0 ) /* multiplication by 1 */
1383c5bb8e1Sralph goto zapright;
139*61c78690Sdonn /* c2 will turn 'i << 1' into 'i + i' for us */
140a9d74daaSmckusick else {
141a9d74daaSmckusick p->in.op = (asgop(o) ? ASG LS : LS);
142a9d74daaSmckusick o = p->in.op;
1433c5bb8e1Sralph p->in.right->in.type = p->in.right->fn.csiz = INT;
1443c5bb8e1Sralph RV(p) = i;
1453c5bb8e1Sralph }
146a9d74daaSmckusick }
1473c5bb8e1Sralph
1483c5bb8e1Sralph /* change +'s of negative consts back to - */
1493c5bb8e1Sralph if( o==PLUS && nncon(p->in.right) && RV(p)<0 ){
1503c5bb8e1Sralph RV(p) = -RV(p);
1513c5bb8e1Sralph o = p->in.op = MINUS;
1523c5bb8e1Sralph }
153fa03d3fbSralph /* FALL THROUGH */
154a9d74daaSmckusick case ASG AND:
155a9d74daaSmckusick case ASG PLUS:
156a9d74daaSmckusick case ASG MINUS:
157fa03d3fbSralph case RS:
158fa03d3fbSralph case LS:
159a9d74daaSmckusick /* Operations with zero */
160a9d74daaSmckusick if( nncon(p->in.right) && RV(p) == 0 ) {
161a9d74daaSmckusick if( o == MUL || o == ASG MUL ||
162a9d74daaSmckusick o == AND || o == ASG AND ) {
163a9d74daaSmckusick if( asgop(o) )
164a9d74daaSmckusick p->in.op = ASSIGN;
165a9d74daaSmckusick else if( optype(LO(p)) == LTYPE ) {
166a9d74daaSmckusick p->in.op = FREE;
167a9d74daaSmckusick LO(p) = FREE;
168a9d74daaSmckusick p = p->in.right;
169a9d74daaSmckusick }
170a9d74daaSmckusick else
171a9d74daaSmckusick p->in.op = COMOP; /* side effects */
172a9d74daaSmckusick }
173a9d74daaSmckusick else if( o == PLUS || o == MINUS ||
174a9d74daaSmckusick o == ASG PLUS || o == ASG MINUS ||
175a9d74daaSmckusick o == OR || o == ER ||
176a9d74daaSmckusick o == LS || o == RS )
177a9d74daaSmckusick goto zapright;
178fa03d3fbSralph }
179*61c78690Sdonn if( o != LS && o != RS )
180*61c78690Sdonn break;
181*61c78690Sdonn /* FALL THROUGH */
182*61c78690Sdonn
183*61c78690Sdonn case ASG RS:
184*61c78690Sdonn case ASG LS:
185*61c78690Sdonn if( !ISUNSIGNED(p->in.left->in.type) )
186*61c78690Sdonn break;
187*61c78690Sdonn if( p->in.right->in.op == ICON &&
188*61c78690Sdonn p->in.right->tn.lval < 0 ) {
189*61c78690Sdonn /*
190*61c78690Sdonn * Technically negative shifts are illegal
191*61c78690Sdonn * but we can support them, at least with
192*61c78690Sdonn * constants; you take potluck with variables.
193*61c78690Sdonn */
194*61c78690Sdonn p->in.right->tn.lval = -p->in.right->tn.lval;
195*61c78690Sdonn switch( o ){
196*61c78690Sdonn case LS: p->in.op = RS; break;
197*61c78690Sdonn case ASG LS: p->in.op = ASG RS; break;
198*61c78690Sdonn case RS: p->in.op = LS; break;
199*61c78690Sdonn case ASG RS: p->in.op = ASG LS; break;
200*61c78690Sdonn }
201*61c78690Sdonn }
202fa03d3fbSralph break;
203fa03d3fbSralph
204a9d74daaSmckusick case ASG DIV:
205a9d74daaSmckusick case DIV:
206a9d74daaSmckusick if( nncon( p->in.right ) ){
207a9d74daaSmckusick if( RV(p) == 0 ) uerror("division by zero");
208a9d74daaSmckusick else if( RV(p) == 1 ) goto zapright;
209a9d74daaSmckusick /* Unsigned division by a power of two */
210a9d74daaSmckusick else if( (i=ispow2(RV(p)))>=0 &&
211a9d74daaSmckusick (ISUNSIGNED(p->in.left->in.type) ||
212a9d74daaSmckusick ISUNSIGNED(p->in.right->in.type)) ){
213a9d74daaSmckusick p->in.op = (asgop(o) ? ASG RS : RS);
214a9d74daaSmckusick p->in.right->in.type = p->in.right->fn.csiz = INT;
215a9d74daaSmckusick RV(p) = i;
216a9d74daaSmckusick }
217a9d74daaSmckusick }
218a9d74daaSmckusick break;
219a9d74daaSmckusick
220a9d74daaSmckusick case ASG MOD:
221fa03d3fbSralph case MOD:
222a9d74daaSmckusick if( nncon(p->in.right) ){
223a9d74daaSmckusick if( RV(p) == 0 ) uerror("modulus of zero");
224a9d74daaSmckusick else if( RV(p) == 1 ){ /* mod by one gives zero */
225a9d74daaSmckusick RV(p) = 0;
226a9d74daaSmckusick if( asgop(o) )
227a9d74daaSmckusick p->in.op = ASSIGN;
228a9d74daaSmckusick else if( optype(LO(p)) == LTYPE ) {
229a9d74daaSmckusick p->in.op = FREE;
230a9d74daaSmckusick LO(p) = FREE;
231a9d74daaSmckusick p = p->in.right;
232a9d74daaSmckusick }
233a9d74daaSmckusick else
234a9d74daaSmckusick p->in.op = COMOP; /* side effects */
235a9d74daaSmckusick }
236a9d74daaSmckusick else if ((i=ispow2(RV(p)))>=0 &&
237a9d74daaSmckusick (ISUNSIGNED(p->in.left->in.type) ||
238a9d74daaSmckusick ISUNSIGNED(p->in.right->in.type)) ){
239a9d74daaSmckusick /* Unsigned mod by a power of two */
240a9d74daaSmckusick p->in.op = (asgop(o) ? ASG AND : AND);
241fa03d3fbSralph RV(p)--;
242fa03d3fbSralph }
243a9d74daaSmckusick }
2443c5bb8e1Sralph break;
2453c5bb8e1Sralph
2463c5bb8e1Sralph case EQ:
2473c5bb8e1Sralph case NE:
2483c5bb8e1Sralph case LT:
2493c5bb8e1Sralph case LE:
2503c5bb8e1Sralph case GT:
2513c5bb8e1Sralph case GE:
2523c5bb8e1Sralph case ULT:
2533c5bb8e1Sralph case ULE:
2543c5bb8e1Sralph case UGT:
2553c5bb8e1Sralph case UGE:
2563c5bb8e1Sralph if( !LCON(p) ) break;
2573c5bb8e1Sralph
2583c5bb8e1Sralph /* exchange operands */
2593c5bb8e1Sralph
2603c5bb8e1Sralph sp = p->in.left;
2613c5bb8e1Sralph p->in.left = p->in.right;
2623c5bb8e1Sralph p->in.right = sp;
2633c5bb8e1Sralph p->in.op = revrel[p->in.op - EQ ];
2643c5bb8e1Sralph break;
2653c5bb8e1Sralph
2663c5bb8e1Sralph }
2673c5bb8e1Sralph
2683c5bb8e1Sralph return(p);
2693c5bb8e1Sralph }
2703c5bb8e1Sralph
ispow2(c)2713c5bb8e1Sralph ispow2( c ) CONSZ c; {
2723c5bb8e1Sralph register i;
2733c5bb8e1Sralph if( c <= 0 || (c&(c-1)) ) return(-1);
2743c5bb8e1Sralph for( i=0; c>1; ++i) c >>= 1;
2753c5bb8e1Sralph return(i);
2763c5bb8e1Sralph }
277