changelog shortlog tags branches changeset files revisions annotate raw help

Mercurial > hg > plan9front / sys/src/cmd/7c/peep.c

changeset 7169: 94fca26a23d8
parent: 1c857cff1d86
author: cinap_lenrek@felloff.net
date: Wed, 17 Apr 2019 23:38:00 +0200
permissions: -rw-r--r--
description: 7c: fix long to vlong/pointer conversion, avoid negative immediate offsets

we have to explicitely convert to vlong by sign or
zero extending as not every operation leaves a proper
zero/sign extended result in the register. for example
NEGW will zero extend, breaking negative int offsets
on pointers.

we explicitely insert SXTW or MOVWU instructions which
the peephole optimizer takes out again when it is safe
todo so.

when promoting constant offsets to immediate offsets,
make sure the offset will be in range. otherwise the
linker will produce not so optimal pointer arithmetic
instructions to calculate the offset.
1 #include "gc.h"
2 
3 int xtramodes(Reg*, Adr*);
4 
5 Reg* findpre(Reg *r, Adr *v);
6 Reg* findinc(Reg *r, Reg *r2, Adr *v);
7 
8 void
9 peep(void)
10 {
11  Reg *r, *r1, *r2;
12  Prog *p, *p1;
13  int t;
14 /*
15  * complete R structure
16  */
17  t = 0;
18  for(r=firstr; r!=R; r=r1) {
19  r1 = r->link;
20  if(r1 == R)
21  break;
22  p = r->prog->link;
23  while(p != r1->prog)
24  switch(p->as) {
25  default:
26  r2 = rega();
27  r->link = r2;
28  r2->link = r1;
29 
30  r2->prog = p;
31  r2->p1 = r;
32  r->s1 = r2;
33  r2->s1 = r1;
34  r1->p1 = r2;
35 
36  r = r2;
37  t++;
38 
39  case ADATA:
40  case AGLOBL:
41  case ANAME:
42  case ASIGNAME:
43  p = p->link;
44  }
45  }
46 
47 loop1:
48  t = 0;
49  for(r=firstr; r!=R; r=r->link) {
50  p = r->prog;
51  if(p->as == ALSL || p->as == ALSR || p->as == AASR ||
52  p->as == ALSLW || p->as == ALSRW || p->as == AASRW) {
53  /*
54  * elide shift into D_SHIFT operand of subsequent instruction
55  */
56  if(0 && shiftprop(r)) {
57  excise(r);
58  t++;
59  }
60  }
61  if(p->as == ASXTW){
62  r1 = findpre(r, &p->from);
63  if(r1 != R){
64  p1 = r1->prog;
65  switch(p1->as){
66  case AMOVB:
67  case AMOVBU:
68  case AMOVH:
69  case AMOVHU:
70  case AMOVW:
71  p->as = AMOVW;
72  break;
73  }
74  }
75  }
76  if(p->as == AMOV || p->as == AMOVW || p->as == AFMOVS || p->as == AFMOVD)
77  if(regtyp(&p->to)) {
78  if(p->from.type == D_CONST)
79  constprop(&p->from, &p->to, r->s1);
80  else if(regtyp(&p->from))
81  if(p->from.type == p->to.type) {
82  if(copyprop(r)) {
83  excise(r);
84  t++;
85  } else
86  if(subprop(r) && copyprop(r)) {
87  excise(r);
88  t++;
89  }
90  }
91  if(regzer(&p->from))
92  if(p->to.type == D_REG) {
93  p->from.type = D_REG;
94  p->from.reg = REGZERO;
95  if(copyprop(r)) {
96  excise(r);
97  t++;
98  } else
99  if(subprop(r) && copyprop(r)) {
100  excise(r);
101  t++;
102  }
103  }
104  }
105  }
106  if(t)
107  goto loop1;
108  /*
109  * look for MOVB x,R; MOVB R,R
110  */
111  for(r=firstr; r!=R; r=r->link) {
112  p = r->prog;
113  switch(p->as) {
114  default:
115  continue;
116  case AEOR:
117  /*
118  * EOR -1,x,y => MVN x,y
119  */
120  if(p->from.type == D_CONST && p->from.offset == -1) {
121  p->as = AMVN;
122  p->from.type = D_REG;
123  if(p->reg != NREG)
124  p->from.reg = p->reg;
125  else
126  p->from.reg = p->to.reg;
127  p->reg = NREG;
128  }
129  continue;
130  case AEORW:
131  /*
132  * EOR -1,x,y => MVN x,y
133  */
134  if(p->from.type == D_CONST && (p->from.offset&0xFFFFFFFF)==0xFFFFFFFF){
135  p->as = AMVNW;
136  p->from.type = D_REG;
137  if(p->reg != NREG)
138  p->from.reg = p->reg;
139  else
140  p->from.reg = p->to.reg;
141  p->reg = NREG;
142  }
143  continue;
144  case AMOVH:
145  case AMOVHU:
146  case AMOVB:
147  case AMOVBU:
148  case AMOVW:
149  case AMOVWU:
150  if(p->to.type != D_REG)
151  continue;
152  break;
153  }
154  r1 = r->link;
155  if(r1 == R)
156  continue;
157  p1 = r1->prog;
158  if(p1->as != p->as)
159  continue;
160  if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
161  continue;
162  if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
163  continue;
164  excise(r1);
165  }
166 
167 #ifdef NOTYET
168  for(r=firstr; r!=R; r=r->link) {
169  p = r->prog;
170  switch(p->as) {
171  case AMOVW:
172  case AMOVB:
173  case AMOVBU:
174  if(p->from.type == D_OREG && p->from.offset == 0)
175  xtramodes(r, &p->from);
176  else if(p->to.type == D_OREG && p->to.offset == 0)
177  xtramodes(r, &p->to);
178  else
179  continue;
180  break;
181  case ACMP:
182  /*
183  * elide CMP $0,x if calculation of x can set condition codes
184  */
185  if(p->from.type != D_CONST || p->from.offset != 0)
186  continue;
187  r2 = r->s1;
188  if(r2 == R)
189  continue;
190  t = r2->prog->as;
191  switch(t) {
192  default:
193  continue;
194  case ABEQ:
195  case ABNE:
196  case ABMI:
197  case ABPL:
198  break;
199  case ABGE:
200  t = ABPL;
201  break;
202  case ABLT:
203  t = ABMI;
204  break;
205  case ABHI:
206  t = ABNE;
207  break;
208  case ABLS:
209  t = ABEQ;
210  break;
211  }
212  r1 = r;
213  do
214  r1 = uniqp(r1);
215  while (r1 != R && r1->prog->as == ANOP);
216  if(r1 == R)
217  continue;
218  p1 = r1->prog;
219  if(p1->to.type != D_REG)
220  continue;
221  if(p1->to.reg != p->reg)
222  if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg))
223  continue;
224  switch(p1->as) {
225  default:
226  continue;
227  case AMOVW:
228  if(p1->from.type != D_REG)
229  continue;
230  case AAND:
231  case AEOR:
232  case AORR:
233  case ABIC:
234  case AMVN:
235  case ASUB:
236  case AADD:
237  case AADC:
238  case ASBC:
239  break;
240  }
241  p1->scond |= C_SBIT;
242  r2->prog->as = t;
243  excise(r);
244  continue;
245  }
246  }
247 #endif
248 
249 #ifdef XXX
250  predicate();
251 #endif
252 }
253 
254 void
255 excise(Reg *r)
256 {
257  Prog *p;
258 
259  p = r->prog;
260  p->as = ANOP;
261  p->scond = zprog.scond;
262  p->from = zprog.from;
263  p->to = zprog.to;
264  p->reg = zprog.reg; /**/
265 }
266 
267 Reg*
268 uniqp(Reg *r)
269 {
270  Reg *r1;
271 
272  r1 = r->p1;
273  if(r1 == R) {
274  r1 = r->p2;
275  if(r1 == R || r1->p2link != R)
276  return R;
277  } else
278  if(r->p2 != R)
279  return R;
280  return r1;
281 }
282 
283 Reg*
284 uniqs(Reg *r)
285 {
286  Reg *r1;
287 
288  r1 = r->s1;
289  if(r1 == R) {
290  r1 = r->s2;
291  if(r1 == R)
292  return R;
293  } else
294  if(r->s2 != R)
295  return R;
296  return r1;
297 }
298 
299 /*
300  * convert references to $0 to references to ZR (REGZERO)
301  */
302 int
303 regzer(Adr *a)
304 {
305 return 0;
306  switch(a->type){
307  case D_CONST:
308  return a->sym == S && a->offset == 0;
309  case D_REG:
310  return a->reg == REGZERO;
311  }
312  return 0;
313 }
314 
315 int
316 regtyp(Adr *a)
317 {
318 
319  if(a->type == D_REG){
320  if(a->reg == REGZERO)
321  return 0;
322  return 1;
323  }
324  if(a->type == D_FREG)
325  return 1;
326  return 0;
327 }
328 
329 /*
330  * the idea is to substitute
331  * one register for another
332  * from one MOV to another
333  * MOV a, R0
334  * ADD b, R0 / no use of R1
335  * MOV R0, R1
336  * would be converted to
337  * MOV a, R1
338  * ADD b, R1
339  * MOV R1, R0
340  * hopefully, then the former or latter MOV
341  * will be eliminated by copy propagation.
342  */
343 int
344 subprop(Reg *r0)
345 {
346  Prog *p;
347  Adr *v1, *v2;
348  Reg *r;
349  int t;
350 
351  p = r0->prog;
352  v1 = &p->from;
353  if(!regtyp(v1))
354  return 0;
355  v2 = &p->to;
356  if(!regtyp(v2))
357  return 0;
358  for(r=uniqp(r0); r!=R; r=uniqp(r)) {
359  if(uniqs(r) == R)
360  break;
361  p = r->prog;
362  switch(p->as) {
363  case ABL:
364  return 0;
365 
366  case ACMP:
367  case ACMN:
368  case AADC:
369  case AADCS:
370  case AADD:
371  case AADDS:
372  case ASUB:
373  case ASUBS:
374  case ALSL:
375  case ALSR:
376  case AASR:
377  case AORR:
378  case AAND:
379  case AANDS:
380  case AEOR:
381  case AMUL:
382  case ASDIV:
383  case AUDIV:
384  case AREM:
385  case AUREM:
386 
387  case ACMPW:
388  case ACMNW:
389  case AADCW:
390  case AADCSW:
391  case AADDSW:
392  case AADDW:
393  case ASUBSW:
394  case ASUBW:
395  case ALSLW:
396  case ALSRW:
397  case AASRW:
398  case AORRW:
399  case AANDW:
400  case AANDSW:
401  case AEORW:
402  case AMULW:
403  case ASDIVW:
404  case AUDIVW:
405  case AREMW:
406  case AUREMW:
407 
408  case AFCMPS:
409  case AFCMPD:
410  case AFADDD:
411  case AFADDS:
412  case AFSUBD:
413  case AFSUBS:
414  case AFMULD:
415  case AFMULS:
416  case AFDIVD:
417  case AFDIVS:
418  if(p->to.type == v1->type)
419  if(p->to.reg == v1->reg) {
420  if(p->reg == NREG)
421  p->reg = p->to.reg;
422  goto gotit;
423  }
424  break;
425 
426  case ANEG:
427  case ANEGS:
428  case ANEGSW:
429  case ANEGW:
430  case ANGC:
431  case ANGCS:
432  case ANGCSW:
433  case ANGCW:
434  case AMVN:
435  case AMVNW:
436  case AFNEGD:
437  case AFNEGS:
438  case AFABSS:
439  case AFABSD:
440  case AFSQRTS:
441  case AFSQRTD:
442  case AFMOVS:
443  case AFMOVD:
444  case AMOVW:
445  case AMOV:
446  case ASXTW:
447  if(p->to.type == v1->type)
448  if(p->to.reg == v1->reg)
449  goto gotit;
450  break;
451 
452  }
453  if(copyau(&p->from, v2) ||
454  copyau1(p, v2) ||
455  copyau(&p->to, v2))
456  break;
457  if(copysub(&p->from, v1, v2, 0) ||
458  copysub1(p, v1, v2, 0) ||
459  copysub(&p->to, v1, v2, 0))
460  break;
461  }
462  return 0;
463 
464 gotit:
465  copysub(&p->to, v1, v2, 1);
466  if(debug['P']) {
467  print("gotit: %D->%D\n%P", v1, v2, r->prog);
468  if(p->from.type == v2->type)
469  print(" excise");
470  print("\n");
471  }
472  for(r=uniqs(r); r!=r0; r=uniqs(r)) {
473  p = r->prog;
474  copysub(&p->from, v1, v2, 1);
475  copysub1(p, v1, v2, 1);
476  copysub(&p->to, v1, v2, 1);
477  if(debug['P'])
478  print("%P\n", r->prog);
479  }
480  t = v1->reg;
481  v1->reg = v2->reg;
482  v2->reg = t;
483  if(debug['P'])
484  print("%P last\n", r->prog);
485  return 1;
486 }
487 
488 /*
489  * The idea is to remove redundant copies.
490  * v1->v2 F=0
491  * (use v2 s/v2/v1/)*
492  * set v1 F=1
493  * use v2 return fail
494  * -----------------
495  * v1->v2 F=0
496  * (use v2 s/v2/v1/)*
497  * set v1 F=1
498  * set v2 return success
499  */
500 int
501 copyprop(Reg *r0)
502 {
503  Prog *p;
504  Adr *v1, *v2;
505  Reg *r;
506 
507  p = r0->prog;
508  v1 = &p->from;
509  v2 = &p->to;
510  if(copyas(v1, v2))
511  return 1;
512  for(r=firstr; r!=R; r=r->link)
513  r->active = 0;
514  return copy1(v1, v2, r0->s1, 0);
515 }
516 
517 int
518 copy1(Adr *v1, Adr *v2, Reg *r, int f)
519 {
520  int t;
521  Prog *p;
522 
523  if(r->active) {
524  if(debug['P'])
525  print("act set; return 1\n");
526  return 1;
527  }
528  r->active = 1;
529  if(debug['P'])
530  print("copy %D->%D f=%d\n", v1, v2, f);
531  for(; r != R; r = r->s1) {
532  p = r->prog;
533  if(debug['P'])
534  print("%P", p);
535  if(!f && uniqp(r) == R) {
536  f = 1;
537  if(debug['P'])
538  print("; merge; f=%d", f);
539  }
540  t = copyu(p, v2, A);
541  switch(t) {
542  case 2: /* rar, cant split */
543  if(debug['P'])
544  print("; %Drar; return 0\n", v2);
545  return 0;
546 
547  case 3: /* set */
548  if(debug['P'])
549  print("; %Dset; return 1\n", v2);
550  return 1;
551 
552  case 1: /* used, substitute */
553  case 4: /* use and set */
554  if(f) {
555  if(!debug['P'])
556  return 0;
557  if(t == 4)
558  print("; %Dused+set and f=%d; return 0\n", v2, f);
559  else
560  print("; %Dused and f=%d; return 0\n", v2, f);
561  return 0;
562  }
563  if(copyu(p, v2, v1)) {
564  if(debug['P'])
565  print("; sub fail; return 0\n");
566  return 0;
567  }
568  if(debug['P'])
569  print("; sub%D/%D", v2, v1);
570  if(t == 4) {
571  if(debug['P'])
572  print("; %Dused+set; return 1\n", v2);
573  return 1;
574  }
575  break;
576  }
577  if(!f) {
578  t = copyu(p, v1, A);
579  if(!f && (t == 2 || t == 3 || t == 4)) {
580  f = 1;
581  if(debug['P'])
582  print("; %Dset and !f; f=%d", v1, f);
583  }
584  }
585  if(debug['P'])
586  print("\n");
587  if(r->s2)
588  if(!copy1(v1, v2, r->s2, f))
589  return 0;
590  }
591  return 1;
592 }
593 
594 /*
595  * The idea is to remove redundant constants.
596  * $c1->v1
597  * ($c1->v2 s/$c1/v1)*
598  * set v1 return
599  * The v1->v2 should be eliminated by copy propagation.
600  */
601 void
602 constprop(Adr *c1, Adr *v1, Reg *r)
603 {
604  Prog *p;
605 
606  if(debug['C'])
607  print("constprop %D->%D\n", c1, v1);
608  for(; r != R; r = r->s1) {
609  p = r->prog;
610  if(debug['C'])
611  print("%P", p);
612  if(uniqp(r) == R) {
613  if(debug['C'])
614  print("; merge; return\n");
615  return;
616  }
617  if(p->as == AMOVW && copyas(&p->from, c1)) {
618  if(debug['C'])
619  print("; sub%D/%D", &p->from, v1);
620  p->from = *v1;
621  } else if(copyu(p, v1, A) > 1) {
622  if(debug['C'])
623  print("; %Dset; return\n", v1);
624  return;
625  }
626  if(debug['C'])
627  print("\n");
628  if(r->s2)
629  constprop(c1, v1, r->s2);
630  }
631 }
632 
633 /*
634  * ALSL x,y,w
635  * .. (not use w, not set x y w)
636  * AXXX w,a,b (a != w)
637  * .. (not use w)
638  * (set w)
639  * ----------- changed to
640  * ..
641  * AXXX (x<<y),a,b
642  * ..
643  */
644 #define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; }
645 int
646 shiftprop(Reg *r)
647 {
648  Reg *r1;
649  Prog *p, *p1, *p2;
650  int n, o;
651  Adr a;
652 
653  p = r->prog;
654  if(p->to.type != D_REG)
655  FAIL("BOTCH: result not reg");
656  n = p->to.reg;
657  a = zprog.from;
658  if(p->reg != NREG && p->reg != p->to.reg) {
659  a.type = D_REG;
660  a.reg = p->reg;
661  }
662  if(debug['H'])
663  print("shiftprop\n%P", p);
664  r1 = r;
665  for(;;) {
666  /* find first use of shift result; abort if shift operands or result are changed */
667  r1 = uniqs(r1);
668  if(r1 == R)
669  FAIL("branch");
670  if(uniqp(r1) == R)
671  FAIL("merge");
672  p1 = r1->prog;
673  if(debug['H'])
674  print("\n%P", p1);
675  switch(copyu(p1, &p->to, A)) {
676  case 0: /* not used or set */
677  if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) ||
678  (a.type == D_REG && copyu(p1, &a, A) > 1))
679  FAIL("args modified");
680  continue;
681  case 3: /* set, not used */
682  FAIL("BOTCH: noref");
683  }
684  break;
685  }
686  /* check whether substitution can be done */
687  switch(p1->as) {
688  case ABIC:
689  case ACMP:
690  case ACMN:
691  if(p1->reg == n)
692  FAIL("can't swap");
693  if(p1->reg == NREG && p1->to.reg == n)
694  FAIL("shift result used twice");
695  case AMVN:
696  if(p1->from.type == D_SHIFT)
697  FAIL("shift result used in shift");
698  if(p1->from.type != D_REG || p1->from.reg != n)
699  FAIL("BOTCH: where is it used?");
700  break;
701  }
702  /* check whether shift result is used subsequently */
703  p2 = p1;
704  if(p1->to.reg != n)
705  for (;;) {
706  r1 = uniqs(r1);
707  if(r1 == R)
708  FAIL("inconclusive");
709  p1 = r1->prog;
710  if(debug['H'])
711  print("\n%P", p1);
712  switch(copyu(p1, &p->to, A)) {
713  case 0: /* not used or set */
714  continue;
715  case 3: /* set, not used */
716  break;
717  default:/* used */
718  FAIL("reused");
719  }
720  break;
721  }
722  /* make the substitution */
723  p2->from.type = D_SHIFT;
724  p2->from.reg = NREG;
725  o = p->reg;
726  if(o == NREG)
727  o = p->to.reg;
728  switch(p->from.type){
729  case D_CONST:
730  o |= (p->from.offset&0x3f)<<7;
731  break;
732  case D_REG:
733  o |= (1<<4) | (p->from.reg<<8);
734  break;
735  }
736  switch(p->as){
737  case ALSL:
738  o |= 0<<5;
739  break;
740  case ALSR:
741  o |= 1<<5;
742  break;
743  case AASR:
744  o |= 2<<5;
745  break;
746  }
747  p2->from.offset = o;
748  if(debug['H'])
749  print("\t=>%P\tSUCCEED\n", p2);
750  return 1;
751 }
752 
753 Reg*
754 findpre(Reg *r, Adr *v)
755 {
756  Reg *r1;
757 
758  for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) {
759  if(uniqs(r1) != r)
760  return R;
761  switch(copyu(r1->prog, v, A)) {
762  case 1: /* used */
763  case 2: /* read-alter-rewrite */
764  return R;
765  case 3: /* set */
766  case 4: /* set and used */
767  return r1;
768  }
769  }
770  return R;
771 }
772 
773 Reg*
774 findinc(Reg *r, Reg *r2, Adr *v)
775 {
776  Reg *r1;
777  Prog *p;
778 
779 
780  for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) {
781  if(uniqp(r1) != r)
782  return R;
783  switch(copyu(r1->prog, v, A)) {
784  case 0: /* not touched */
785  continue;
786  case 4: /* set and used */
787  p = r1->prog;
788  if(p->as == AADD)
789  if(p->from.type == D_CONST)
790  if(p->from.offset > -256 && p->from.offset < 256)
791  return r1;
792  default:
793  return R;
794  }
795  }
796  return R;
797 }
798 
799 int
800 nochange(Reg *r, Reg *r2, Prog *p)
801 {
802  Adr a[3];
803  int i, n;
804 
805  if(r == r2)
806  return 1;
807  n = 0;
808  if(p->reg != NREG && p->reg != p->to.reg) {
809  a[n].type = D_REG;
810  a[n++].reg = p->reg;
811  }
812  switch(p->from.type) {
813  case D_SHIFT:
814  a[n].type = D_REG;
815  a[n++].reg = p->from.offset&0xf;
816  case D_REG:
817  a[n].type = D_REG;
818  a[n++].reg = p->from.reg;
819  }
820  if(n == 0)
821  return 1;
822  for(; r!=R && r!=r2; r=uniqs(r)) {
823  p = r->prog;
824  for(i=0; i<n; i++)
825  if(copyu(p, &a[i], A) > 1)
826  return 0;
827  }
828  return 1;
829 }
830 
831 int
832 findu1(Reg *r, Adr *v)
833 {
834  for(; r != R; r = r->s1) {
835  if(r->active)
836  return 0;
837  r->active = 1;
838  switch(copyu(r->prog, v, A)) {
839  case 1: /* used */
840  case 2: /* read-alter-rewrite */
841  case 4: /* set and used */
842  return 1;
843  case 3: /* set */
844  return 0;
845  }
846  if(r->s2)
847  if (findu1(r->s2, v))
848  return 1;
849  }
850  return 0;
851 }
852 
853 int
854 finduse(Reg *r, Adr *v)
855 {
856  Reg *r1;
857 
858  for(r1=firstr; r1!=R; r1=r1->link)
859  r1->active = 0;
860  return findu1(r, v);
861 }
862 
863 #ifdef NOTYET
864 int
865 xtramodes(Reg *r, Adr *a)
866 {
867  Reg *r1, *r2, *r3;
868  Prog *p, *p1;
869  Adr v;
870 
871  p = r->prog;
872  if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG) /* byte load */
873  return 0;
874  v = *a;
875  v.type = D_REG;
876  r1 = findpre(r, &v);
877  if(r1 != R) {
878  p1 = r1->prog;
879  if(p1->to.type == D_REG && p1->to.reg == v.reg)
880  switch(p1->as) {
881  case AADD:
882  if(p1->from.type == D_REG ||
883  (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
884  (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
885  (p1->from.type == D_CONST &&
886  p1->from.offset > -4096 && p1->from.offset < 4096))
887  if(nochange(uniqs(r1), r, p1)) {
888  if(a != &p->from || v.reg != p->to.reg)
889  if (finduse(r->s1, &v)) {
890  if(p1->reg == NREG || p1->reg == v.reg)
891  /* pre-indexing */
892  p->scond |= C_WBIT;
893  else return 0;
894  }
895  switch (p1->from.type) {
896  case D_REG:
897  /* register offset */
898  a->type = D_SHIFT;
899  a->offset = p1->from.reg;
900  break;
901  case D_SHIFT:
902  /* scaled register offset */
903  a->type = D_SHIFT;
904  case D_CONST:
905  /* immediate offset */
906  a->offset = p1->from.offset;
907  break;
908  }
909  if(p1->reg != NREG)
910  a->reg = p1->reg;
911  excise(r1);
912  return 1;
913  }
914  break;
915  case AMOVW:
916  if(p1->from.type == D_REG)
917  if((r2 = findinc(r1, r, &p1->from)) != R) {
918  for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
919  ;
920  if(r3 == r) {
921  /* post-indexing */
922  p1 = r2->prog;
923  a->reg = p1->to.reg;
924  a->offset = p1->from.offset;
925  p->scond |= C_PBIT;
926  if(!finduse(r, &r1->prog->to))
927  excise(r1);
928  excise(r2);
929  return 1;
930  }
931  }
932  break;
933  }
934  }
935  if(a != &p->from || a->reg != p->to.reg)
936  if((r1 = findinc(r, R, &v)) != R) {
937  /* post-indexing */
938  p1 = r1->prog;
939  a->offset = p1->from.offset;
940  p->scond |= C_PBIT;
941  excise(r1);
942  return 1;
943  }
944  return 0;
945 }
946 #endif
947 
948 /*
949  * return
950  * 1 if v only used (and substitute),
951  * 2 if read-alter-rewrite
952  * 3 if set
953  * 4 if set and used
954  * 0 otherwise (not touched)
955  */
956 int
957 copyu(Prog *p, Adr *v, Adr *s)
958 {
959 
960  switch(p->as) {
961 
962  default:
963  if(debug['P'])
964  print(" (unk)");
965  return 2;
966 
967  case ANOP: /* read, write */
968  case AFMOVS:
969  case AFMOVD:
970  case AMOVH:
971  case AMOVHU:
972  case AMOVB:
973  case AMOVBU:
974  case AMOVW:
975  case AMOVWU:
976  case ASXTW:
977  case AMOV:
978  case AMVN:
979  case AMVNW:
980  case ANEG:
981  case ANEGS:
982  case ANEGW:
983  case ANEGSW:
984  case ANGC:
985  case ANGCS:
986  case ANGCW:
987  case ANGCSW:
988  case AFCVTSD:
989  case AFCVTDS:
990  case AFCVTZSD:
991  case AFCVTZSDW:
992  case AFCVTZSS:
993  case AFCVTZSSW:
994  case AFCVTZUD:
995  case AFCVTZUDW:
996  case AFCVTZUS:
997  case AFCVTZUSW:
998  case ASCVTFD:
999  case ASCVTFS:
1000  case ASCVTFWD:
1001  case ASCVTFWS:
1002  case AUCVTFD:
1003  case AUCVTFS:
1004  case AUCVTFWD:
1005  case AUCVTFWS:
1006  case AFNEGD:
1007  case AFNEGS:
1008  case AFABSD:
1009  case AFABSS:
1010  case AFSQRTD:
1011  case AFSQRTS:
1012  case ACASE:
1013 #ifdef YYY
1014  if(p->scond&(C_WBIT|C_PBIT))
1015  if(v->type == D_REG) {
1016  if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
1017  if(p->from.reg == v->reg)
1018  return 2;
1019  } else {
1020  if(p->to.reg == v->reg)
1021  return 2;
1022  }
1023  }
1024 #endif
1025  if(s != A) {
1026  if(copysub(&p->from, v, s, 1))
1027  return 1;
1028  if(!copyas(&p->to, v))
1029  if(copysub(&p->to, v, s, 1))
1030  return 1;
1031  return 0;
1032  }
1033  if(copyas(&p->to, v)) {
1034  if(copyau(&p->from, v))
1035  return 4;
1036  return 3;
1037  }
1038  if(copyau(&p->from, v))
1039  return 1;
1040  if(copyau(&p->to, v))
1041  return 1;
1042  return 0;
1043 
1044 
1045  case AADD: /* read, read, write */
1046  case AADDW:
1047  case AADDS:
1048  case AADDSW:
1049  case ASUB:
1050  case ASUBW:
1051  case ASUBS:
1052  case ASUBSW:
1053  if(0 && p->from.type == D_CONST){
1054  if(s != A && regzer(s))
1055  return 4; /* add/sub $c,r,r -> r31 is sp not zr, don't touch */
1056  }
1057 
1058  case ALSL:
1059  case ALSLW:
1060  case ALSR:
1061  case ALSRW:
1062  case AASR:
1063  case AASRW:
1064  case AORR:
1065  case AORRW:
1066  case AAND:
1067  case AANDW:
1068  case AEOR:
1069  case AEORW:
1070  case AMUL:
1071  case AMULW:
1072  case AUMULL:
1073  case AREM:
1074  case AREMW:
1075  case ASDIV:
1076  case ASDIVW:
1077  case AUDIV:
1078  case AUDIVW:
1079  case AUREM:
1080  case AUREMW:
1081  case AFADDS:
1082  case AFADDD:
1083  case AFSUBS:
1084  case AFSUBD:
1085  case AFMULS:
1086  case AFMULD:
1087  case AFDIVS:
1088  case AFDIVD:
1089  if(s != A) {
1090  if(copysub(&p->from, v, s, 1))
1091  return 1;
1092  if(copysub1(p, v, s, 1))
1093  return 1;
1094  if(!copyas(&p->to, v))
1095  if(copysub(&p->to, v, s, 1))
1096  return 1;
1097  return 0;
1098  }
1099  if(copyas(&p->to, v)) {
1100  if(p->reg == NREG)
1101  p->reg = p->to.reg;
1102  if(copyau(&p->from, v))
1103  return 4;
1104  if(copyau1(p, v))
1105  return 4;
1106  return 3;
1107  }
1108  if(copyau(&p->from, v))
1109  return 1;
1110  if(copyau1(p, v))
1111  return 1;
1112  if(copyau(&p->to, v))
1113  return 1;
1114  return 0;
1115 
1116  case ABEQ: /* read, read */
1117  case ABNE:
1118  case ABCS:
1119  case ABHS:
1120  case ABCC:
1121  case ABLO:
1122  case ABMI:
1123  case ABPL:
1124  case ABVS:
1125  case ABVC:
1126  case ABHI:
1127  case ABLS:
1128  case ABGE:
1129  case ABLT:
1130  case ABGT:
1131  case ABLE:
1132 
1133  case AFCMPS:
1134  case AFCMPD:
1135  case ACMP:
1136  case ACMPW:
1137  case ACMN:
1138  case ACMNW:
1139  if(s != A) {
1140  if(copysub(&p->from, v, s, 1))
1141  return 1;
1142  return copysub1(p, v, s, 1);
1143  }
1144  if(copyau(&p->from, v))
1145  return 1;
1146  if(copyau1(p, v))
1147  return 1;
1148  return 0;
1149 
1150  case AB: /* funny */
1151  if(s != A) {
1152  if(copysub(&p->to, v, s, 1))
1153  return 1;
1154  return 0;
1155  }
1156  if(copyau(&p->to, v))
1157  return 1;
1158  return 0;
1159 
1160  case ARET:
1161  case ARETURN: /* funny */
1162  if(v->type == D_REG)
1163  if(v->reg == REGRET)
1164  return 2;
1165  if(v->type == D_FREG)
1166  if(v->reg == FREGRET)
1167  return 2;
1168 
1169  case ABL: /* funny */
1170  if(v->type == D_REG) {
1171  if(v->reg <= REGEXT && v->reg > exregoffset)
1172  return 2;
1173  if(v->reg == REGARG)
1174  return 2;
1175  }
1176  if(v->type == D_FREG)
1177  if(v->reg <= FREGEXT && v->reg > exfregoffset)
1178  return 2;
1179 
1180  if(s != A) {
1181  if(copysub(&p->to, v, s, 1))
1182  return 1;
1183  return 0;
1184  }
1185  if(copyau(&p->to, v))
1186  return 4;
1187  return 3;
1188 
1189  case ATEXT: /* funny */
1190  if(v->type == D_REG)
1191  if(v->reg == REGARG)
1192  return 3;
1193  return 0;
1194  }
1195 }
1196 
1197 int
1198 a2type(Prog *p)
1199 {
1200 
1201  switch(p->as) {
1202 
1203  case ACMP:
1204  case ACMPW:
1205  case ACMN:
1206  case ACMNW:
1207 
1208  case AADD:
1209  case AADDW:
1210  case AADDS:
1211  case AADDSW:
1212  case ASUB:
1213  case ASUBS:
1214  case ASUBSW:
1215  case ASUBW:
1216  case ALSL:
1217  case ALSLW:
1218  case ALSR:
1219  case ALSRW:
1220  case AASR:
1221  case AASRW:
1222  case AORR:
1223  case AORRW:
1224  case AAND:
1225  case AANDW:
1226  case AANDS:
1227  case AANDSW:
1228  case AEOR:
1229  case AEORW:
1230  case AMUL:
1231  case AMULW:
1232  case AUMULL:
1233  case AREM:
1234  case AREMW:
1235  case ASDIV:
1236  case ASDIVW:
1237  case AUDIV:
1238  case AUDIVW:
1239  case AUREM:
1240  case AUREMW:
1241  return D_REG;
1242 
1243  case AFCMPS:
1244  case AFCMPD:
1245 
1246  case AFADDS:
1247  case AFADDD:
1248  case AFSUBS:
1249  case AFSUBD:
1250  case AFMULS:
1251  case AFMULD:
1252  case AFDIVS:
1253  case AFDIVD:
1254  return D_FREG;
1255  }
1256  return D_NONE;
1257 }
1258 
1259 /*
1260  * direct reference,
1261  * could be set/use depending on
1262  * semantics
1263  */
1264 int
1265 copyas(Adr *a, Adr *v)
1266 {
1267 
1268  if(regtyp(v)) {
1269  if(a->type == v->type)
1270  if(a->reg == v->reg)
1271  return 1;
1272  } else if(v->type == D_CONST) { /* for constprop */
1273  if(a->type == v->type)
1274  if(a->name == v->name)
1275  if(a->sym == v->sym)
1276  if(a->reg == v->reg)
1277  if(a->offset == v->offset)
1278  return 1;
1279  }
1280  return 0;
1281 }
1282 
1283 /*
1284  * either direct or indirect
1285  */
1286 int
1287 copyau(Adr *a, Adr *v)
1288 {
1289 
1290  if(copyas(a, v))
1291  return 1;
1292  if(v->type == D_REG) {
1293  if(a->type == D_OREG) {
1294  if(v->reg == a->reg)
1295  return 1;
1296  } else if(a->type == D_SHIFT) {
1297  if(((a->offset>>16)&0x1F) == v->reg)
1298  return 1;
1299  } else if(a->type == D_EXTREG) {
1300  if(a->reg == v->reg || ((a->offset>>16)&0x1F) == v->reg)
1301  return 1;
1302  }
1303  }
1304  return 0;
1305 }
1306 
1307 int
1308 copyau1(Prog *p, Adr *v)
1309 {
1310 
1311  if(regtyp(v)) {
1312  if(a2type(p) == v->type)
1313  if(p->reg == v->reg) {
1314  if(a2type(p) != v->type)
1315  print("botch a2type %P\n", p);
1316  return 1;
1317  }
1318  }
1319  return 0;
1320 }
1321 
1322 /*
1323  * substitute s for v in a
1324  * return failure to substitute
1325  */
1326 int
1327 copysub(Adr *a, Adr *v, Adr *s, int f)
1328 {
1329 
1330  if(f)
1331  if(copyau(a, v)) {
1332  if(a->type == D_SHIFT) {
1333  if(((a->offset>>16)&0x1F) == v->reg)
1334  a->offset = (a->offset&~(0x1F<<16))|(s->reg<<16);
1335  } else
1336  a->reg = s->reg;
1337  }
1338  return 0;
1339 }
1340 
1341 int
1342 copysub1(Prog *p1, Adr *v, Adr *s, int f)
1343 {
1344 
1345  if(f)
1346  if(copyau1(p1, v))
1347  p1->reg = s->reg;
1348  return 0;
1349 }
1350 
1351 struct {
1352  int opcode;
1353  int notopcode;
1354  int scond;
1355  int notscond;
1356 } predinfo[] = {
1357  { ABEQ, ABNE, 0x0, 0x1, },
1358  { ABNE, ABEQ, 0x1, 0x0, },
1359  { ABCS, ABCC, 0x2, 0x3, },
1360  { ABHS, ABLO, 0x2, 0x3, },
1361  { ABCC, ABCS, 0x3, 0x2, },
1362  { ABLO, ABHS, 0x3, 0x2, },
1363  { ABMI, ABPL, 0x4, 0x5, },
1364  { ABPL, ABMI, 0x5, 0x4, },
1365  { ABVS, ABVC, 0x6, 0x7, },
1366  { ABVC, ABVS, 0x7, 0x6, },
1367  { ABHI, ABLS, 0x8, 0x9, },
1368  { ABLS, ABHI, 0x9, 0x8, },
1369  { ABGE, ABLT, 0xA, 0xB, },
1370  { ABLT, ABGE, 0xB, 0xA, },
1371  { ABGT, ABLE, 0xC, 0xD, },
1372  { ABLE, ABGT, 0xD, 0xC, },
1373 };
1374 
1375 typedef struct {
1376  Reg *start;
1377  Reg *last;
1378  Reg *end;
1379  int len;
1380 } Joininfo;
1381 
1382 enum {
1383  Join,
1384  Split,
1385  End,
1386  Branch,
1387  Setcond,
1388  Toolong
1389 };
1390 
1391 enum {
1392  Falsecond,
1393  Truecond,
1394  Delbranch,
1395  Keepbranch
1396 };
1397 
1398 int
1399 isbranch(Prog *p)
1400 {
1401  return (ABEQ <= p->as) && (p->as <= ABLE);
1402 }
1403 
1404 int
1405 predicable(Prog *p)
1406 {
1407  if (isbranch(p)
1408  || p->as == ANOP
1409  || p->as == AXXX
1410  || p->as == ADATA
1411  || p->as == AGLOBL
1412  || p->as == AGOK
1413  || p->as == AHISTORY
1414  || p->as == ANAME
1415  || p->as == ASIGNAME
1416  || p->as == ATEXT
1417  || p->as == AWORD
1418  || p->as == ADYNT
1419  || p->as == AINIT
1420  || p->as == ABCASE
1421  || p->as == ACASE)
1422  return 0;
1423  return 1;
1424 }
1425 
1426 /*
1427  * Depends on an analysis of the encodings performed by 5l.
1428  * These seem to be all of the opcodes that lead to the "S" bit
1429  * being set in the instruction encodings.
1430  *
1431  * C_SBIT may also have been set explicitly in p->scond.
1432  */
1433 int
1434 modifiescpsr(Prog *p)
1435 {
1436 // return (p->scond&C_SBIT)
1437  return 1
1438  || p->as == ATST
1439  || p->as == ACMN
1440  || p->as == ACMP
1441  || p->as == AUMULL
1442  || p->as == AUDIV
1443  || p->as == AMUL
1444  || p->as == ASDIV
1445  || p->as == AREM
1446  || p->as == AUREM
1447  || p->as == ABL;
1448 }
1449 
1450 /*
1451  * Find the maximal chain of instructions starting with r which could
1452  * be executed conditionally
1453  */
1454 int
1455 joinsplit(Reg *r, Joininfo *j)
1456 {
1457  j->start = r;
1458  j->last = r;
1459  j->len = 0;
1460  do {
1461  if (r->p2 && (r->p1 || r->p2->p2link)) {
1462  j->end = r;
1463  return Join;
1464  }
1465  if (r->s1 && r->s2) {
1466  j->end = r;
1467  return Split;
1468  }
1469  j->last = r;
1470  if (r->prog->as != ANOP)
1471  j->len++;
1472  if (!r->s1 && !r->s2) {
1473  j->end = r->link;
1474  return End;
1475  }
1476  if (r->s2) {
1477  j->end = r->s2;
1478  return Branch;
1479  }
1480  if (modifiescpsr(r->prog)) {
1481  j->end = r->s1;
1482  return Setcond;
1483  }
1484  r = r->s1;
1485  } while (j->len < 4);
1486  j->end = r;
1487  return Toolong;
1488 }
1489 
1490 Reg *
1491 successor(Reg *r)
1492 {
1493  if (r->s1)
1494  return r->s1;
1495  else
1496  return r->s2;
1497 }
1498 
1499 #ifdef XXX
1500 void
1501 applypred(Reg *rstart, Joininfo *j, int cond, int branch)
1502 {
1503  int pred;
1504  Reg *r;
1505 
1506  if(j->len == 0)
1507  return;
1508  if (cond == Truecond)
1509  pred = predinfo[rstart->prog->as - ABEQ].scond;
1510  else
1511  pred = predinfo[rstart->prog->as - ABEQ].notscond;
1512 
1513  for (r = j->start; ; r = successor(r)) {
1514  if (r->prog->as == AB) {
1515  if (r != j->last || branch == Delbranch)
1516  excise(r);
1517  else {
1518  if (cond == Truecond)
1519  r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
1520  else
1521  r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
1522  }
1523  }
1524  else if (predicable(r->prog))
1525  r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
1526  if (r->s1 != r->link) {
1527  r->s1 = r->link;
1528  r->link->p1 = r;
1529  }
1530  if (r == j->last)
1531  break;
1532  }
1533 }
1534 
1535 
1536 void
1537 predicate(void)
1538 {
1539  Reg *r;
1540  int t1, t2;
1541  Joininfo j1, j2;
1542 
1543  for(r=firstr; r!=R; r=r->link) {
1544  if (isbranch(r->prog)) {
1545  t1 = joinsplit(r->s1, &j1);
1546  t2 = joinsplit(r->s2, &j2);
1547  if(j1.last->link != j2.start)
1548  continue;
1549  if(j1.end == j2.end)
1550  if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
1551  (t2 == Join && (t1 == Join || t1 == Setcond))) {
1552  applypred(r, &j1, Falsecond, Delbranch);
1553  applypred(r, &j2, Truecond, Delbranch);
1554  excise(r);
1555  continue;
1556  }
1557  if(t1 == End || t1 == Branch) {
1558  applypred(r, &j1, Falsecond, Keepbranch);
1559  excise(r);
1560  continue;
1561  }
1562  }
1563  }
1564 }
1565 #endif