text: // Inferno utils/5c/peep.c
  // http://code.google.com/p/inferno-os/source/browse/utils/5c/peep.c
  //
  //	Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
  //	Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
  //	Portions Copyright © 1997-1999 Vita Nuova Limited
  //	Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
  //	Portions Copyright © 2004,2006 Bruce Ellis
  //	Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
  //	Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
  //	Portions Copyright © 2009 The Go Authors.  All rights reserved.
  //
  // Permission is hereby granted, free of charge, to any person obtaining a copy
  // of this software and associated documentation files (the "Software"), to deal
  // in the Software without restriction, including without limitation the rights
  // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  // copies of the Software, and to permit persons to whom the Software is
  // furnished to do so, subject to the following conditions:
  //
  // The above copyright notice and this permission notice shall be included in
  // all copies or substantial portions of the Software.
  //
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  // THE SOFTWARE.
  
  
  #include "gc.h"
  
  int xtramodes(Reg*, Adr*);
  
  void
  peep(void)
  {
  	Reg *r, *r1, *r2;
  	Prog *p, *p1;
  	int t;
  /*
   * complete R structure
   */
  	t = 0;
  	for(r=firstr; r!=R; r=r1) {
  		r1 = r->link;
  		if(r1 == R)
  			break;
  		p = r->prog->link;
  		while(p != r1->prog)
  		switch(p->as) {
  		default:
  			r2 = rega();
  			r->link = r2;
  			r2->link = r1;
  
  			r2->prog = p;
  			r2->p1 = r;
  			r->s1 = r2;
  			r2->s1 = r1;
  			r1->p1 = r2;
  
  			r = r2;
  			t++;
  
  		case ADATA:
  		case AGLOBL:
  		case ANAME:
  		case ASIGNAME:
  			p = p->link;
  		}
  	}
  
  loop1:
  	t = 0;
  	for(r=firstr; r!=R; r=r->link) {
  		p = r->prog;
  		if(p->as == ASLL || p->as == ASRL || p->as == ASRA) {
  			/*
  			 * elide shift into D_SHIFT operand of subsequent instruction
  			 */
  			if(shiftprop(r)) {
  				excise(r);
  				t++;
  			}
  		}
  		if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
  		if(regtyp(&p->to)) {
  			if(p->from.type == D_CONST)
  				constprop(&p->from, &p->to, r->s1);
  			else if(regtyp(&p->from))
  			if(p->from.type == p->to.type) {
  				if(copyprop(r)) {
  					excise(r);
  					t++;
  				} else
  				if(subprop(r) && copyprop(r)) {
  					excise(r);
  					t++;
  				}
  			}
  		}
  	}
  	if(t)
  		goto loop1;
  	/*
  	 * look for MOVB x,R; MOVB R,R
  	 */
  	for(r=firstr; r!=R; r=r->link) {
  		p = r->prog;
  		switch(p->as) {
  		default:
  			continue;
  		case AEOR:
  			/*
  			 * EOR -1,x,y => MVN x,y
  			 */
  			if(p->from.type == D_CONST && p->from.offset == -1) {
  				p->as = AMVN;
  				p->from.type = D_REG;
  				if(p->reg != NREG)
  					p->from.reg = p->reg;
  				else
  					p->from.reg = p->to.reg;
  				p->reg = NREG;
  			}
  			continue;
  		case AMOVH:
  		case AMOVHU:
  		case AMOVB:
  		case AMOVBU:
  			if(p->to.type != D_REG)
  				continue;
  			break;
  		}
  		r1 = r->link;
  		if(r1 == R)
  			continue;
  		p1 = r1->prog;
  		if(p1->as != p->as)
  			continue;
  		if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
  			continue;
  		if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
  			continue;
  		excise(r1);
  	}
  
  	for(r=firstr; r!=R; r=r->link) {
  		p = r->prog;
  		switch(p->as) {
  		case AMOVW:
  		case AMOVB:
  		case AMOVBU:
  			if(p->from.type == D_OREG && p->from.offset == 0)
  				xtramodes(r, &p->from);
  			else if(p->to.type == D_OREG && p->to.offset == 0)
  				xtramodes(r, &p->to);
  			else
  				continue;
  			break;
  		case ACMP:
  			/*
  			 * elide CMP $0,x if calculation of x can set condition codes
  			 */
  			if(p->from.type != D_CONST || p->from.offset != 0)
  				continue;
  			r2 = r->s1;
  			if(r2 == R)
  				continue;
  			t = r2->prog->as;
  			switch(t) {
  			default:
  				continue;
  			case ABEQ:
  			case ABNE:
  			case ABMI:
  			case ABPL:
  				break;
  			case ABGE:
  				t = ABPL;
  				break;
  			case ABLT:
  				t = ABMI;
  				break;
  			case ABHI:
  				t = ABNE;
  				break;
  			case ABLS:
  				t = ABEQ;
  				break;
  			}
  			r1 = r;
  			do
  				r1 = uniqp(r1);
  			while (r1 != R && r1->prog->as == ANOP);
  			if(r1 == R)
  				continue;
  			p1 = r1->prog;
  			if(p1->to.type != D_REG)
  				continue;
  			if(p1->to.reg != p->reg)
  			if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg))
  				continue;
  			switch(p1->as) {
  			default:
  				continue;
  			case AMOVW:
  				if(p1->from.type != D_REG)
  					continue;
  			case AAND:
  			case AEOR:
  			case AORR:
  			case ABIC:
  			case AMVN:
  			case ASUB:
  			case ARSB:
  			case AADD:
  			case AADC:
  			case ASBC:
  			case ARSC:
  				break;
  			}
  			p1->scond |= C_SBIT;
  			r2->prog->as = t;
  			excise(r);
  			continue;
  		}
  	}
  
  	predicate();
  }
  
  void
  excise(Reg *r)
  {
  	Prog *p;
  
  	p = r->prog;
  	p->as = ANOP;
  	p->scond = zprog.scond;
  	p->from = zprog.from;
  	p->to = zprog.to;
  	p->reg = zprog.reg; /**/
  }
  
  Reg*
  uniqp(Reg *r)
  {
  	Reg *r1;
  
  	r1 = r->p1;
  	if(r1 == R) {
  		r1 = r->p2;
  		if(r1 == R || r1->p2link != R)
  			return R;
  	} else
  		if(r->p2 != R)
  			return R;
  	return r1;
  }
  
  Reg*
  uniqs(Reg *r)
  {
  	Reg *r1;
  
  	r1 = r->s1;
  	if(r1 == R) {
  		r1 = r->s2;
  		if(r1 == R)
  			return R;
  	} else
  		if(r->s2 != R)
  			return R;
  	return r1;
  }
  
  int
  regtyp(Adr *a)
  {
  
  	if(a->type == D_REG)
  		return 1;
  	if(a->type == D_FREG)
  		return 1;
  	return 0;
  }
  
  /*
   * the idea is to substitute
   * one register for another
   * from one MOV to another
   *	MOV	a, R0
   *	ADD	b, R0	/ no use of R1
   *	MOV	R0, R1
   * would be converted to
   *	MOV	a, R1
   *	ADD	b, R1
   *	MOV	R1, R0
   * hopefully, then the former or latter MOV
   * will be eliminated by copy propagation.
   */
  int
  subprop(Reg *r0)
  {
  	Prog *p;
  	Adr *v1, *v2;
  	Reg *r;
  	int t;
  
  	p = r0->prog;
  	v1 = &p->from;
  	if(!regtyp(v1))
  		return 0;
  	v2 = &p->to;
  	if(!regtyp(v2))
  		return 0;
  	for(r=uniqp(r0); r!=R; r=uniqp(r)) {
  		if(uniqs(r) == R)
  			break;
  		p = r->prog;
  		switch(p->as) {
  		case ABL:
  			return 0;
  
  		case ACMP:
  		case ACMN:
  		case AADD:
  		case ASUB:
  		case ARSB:
  		case ASLL:
  		case ASRL:
  		case ASRA:
  		case AORR:
  		case AAND:
  		case AEOR:
  		case AMUL:
  		case ADIV:
  		case ADIVU:
  
  		case ACMPF:
  		case ACMPD:
  		case AADDD:
  		case AADDF:
  		case ASUBD:
  		case ASUBF:
  		case AMULD:
  		case AMULF:
  		case ADIVD:
  		case ADIVF:
  			if(p->to.type == v1->type)
  			if(p->to.reg == v1->reg) {
  				if(p->reg == NREG)
  					p->reg = p->to.reg;
  				goto gotit;
  			}
  			break;
  
  		case AMOVF:
  		case AMOVD:
  		case AMOVW:
  			if(p->to.type == v1->type)
  			if(p->to.reg == v1->reg)
  				goto gotit;
  			break;
  
  		case AMOVM:
  			t = 1<<v2->reg;
  			if((p->from.type == D_CONST && (p->from.offset&t)) ||
  			   (p->to.type == D_CONST && (p->to.offset&t)))
  				return 0;
  			break;
  		}
  		if(copyau(&p->from, v2) ||
  		   copyau1(p, v2) ||
  		   copyau(&p->to, v2))
  			break;
  		if(copysub(&p->from, v1, v2, 0) ||
  		   copysub1(p, v1, v2, 0) ||
  		   copysub(&p->to, v1, v2, 0))
  			break;
  	}
  	return 0;
  
  gotit:
  	copysub(&p->to, v1, v2, 1);
  	if(debug['P']) {
  		print("gotit: %D->%D\n%P", v1, v2, r->prog);
  		if(p->from.type == v2->type)
  			print(" excise");
  		print("\n");
  	}
  	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
  		p = r->prog;
  		copysub(&p->from, v1, v2, 1);
  		copysub1(p, v1, v2, 1);
  		copysub(&p->to, v1, v2, 1);
  		if(debug['P'])
  			print("%P\n", r->prog);
  	}
  	t = v1->reg;
  	v1->reg = v2->reg;
  	v2->reg = t;
  	if(debug['P'])
  		print("%P last\n", r->prog);
  	return 1;
  }
  
  /*
   * The idea is to remove redundant copies.
   *	v1->v2	F=0
   *	(use v2	s/v2/v1/)*
   *	set v1	F=1
   *	use v2	return fail
   *	-----------------
   *	v1->v2	F=0
   *	(use v2	s/v2/v1/)*
   *	set v1	F=1
   *	set v2	return success
   */
  int
  copyprop(Reg *r0)
  {
  	Prog *p;
  	Adr *v1, *v2;
  	Reg *r;
  
  	p = r0->prog;
  	v1 = &p->from;
  	v2 = &p->to;
  	if(copyas(v1, v2))
  		return 1;
  	for(r=firstr; r!=R; r=r->link)
  		r->active = 0;
  	return copy1(v1, v2, r0->s1, 0);
  }
  
  int
  copy1(Adr *v1, Adr *v2, Reg *r, int f)
  {
  	int t;
  	Prog *p;
  
  	if(r->active) {
  		if(debug['P'])
  			print("act set; return 1\n");
  		return 1;
  	}
  	r->active = 1;
  	if(debug['P'])
  		print("copy %D->%D f=%d\n", v1, v2, f);
  	for(; r != R; r = r->s1) {
  		p = r->prog;
  		if(debug['P'])
  			print("%P", p);
  		if(!f && uniqp(r) == R) {
  			f = 1;
  			if(debug['P'])
  				print("; merge; f=%d", f);
  		}
  		t = copyu(p, v2, A);
  		switch(t) {
  		case 2:	/* rar, cant split */
  			if(debug['P'])
  				print("; %Drar; return 0\n", v2);
  			return 0;
  
  		case 3:	/* set */
  			if(debug['P'])
  				print("; %Dset; return 1\n", v2);
  			return 1;
  
  		case 1:	/* used, substitute */
  		case 4:	/* use and set */
  			if(f) {
  				if(!debug['P'])
  					return 0;
  				if(t == 4)
  					print("; %Dused+set and f=%d; return 0\n", v2, f);
  				else
  					print("; %Dused and f=%d; return 0\n", v2, f);
  				return 0;
  			}
  			if(copyu(p, v2, v1)) {
  				if(debug['P'])
  					print("; sub fail; return 0\n");
  				return 0;
  			}
  			if(debug['P'])
  				print("; sub%D/%D", v2, v1);
  			if(t == 4) {
  				if(debug['P'])
  					print("; %Dused+set; return 1\n", v2);
  				return 1;
  			}
  			break;
  		}
  		if(!f) {
  			t = copyu(p, v1, A);
  			if(!f && (t == 2 || t == 3 || t == 4)) {
  				f = 1;
  				if(debug['P'])
  					print("; %Dset and !f; f=%d", v1, f);
  			}
  		}
  		if(debug['P'])
  			print("\n");
  		if(r->s2)
  			if(!copy1(v1, v2, r->s2, f))
  				return 0;
  	}
  	return 1;
  }
  
  /*
   * The idea is to remove redundant constants.
   *	$c1->v1
   *	($c1->v2 s/$c1/v1)*
   *	set v1  return
   * The v1->v2 should be eliminated by copy propagation.
   */
  void
  constprop(Adr *c1, Adr *v1, Reg *r)
  {
  	Prog *p;
  
  	if(debug['C'])
  		print("constprop %D->%D\n", c1, v1);
  	for(; r != R; r = r->s1) {
  		p = r->prog;
  		if(debug['C'])
  			print("%P", p);
  		if(uniqp(r) == R) {
  			if(debug['C'])
  				print("; merge; return\n");
  			return;
  		}
  		if(p->as == AMOVW && copyas(&p->from, c1)) {
  				if(debug['C'])
  					print("; sub%D/%D", &p->from, v1);
  				p->from = *v1;
  		} else if(copyu(p, v1, A) > 1) {
  			if(debug['C'])
  				print("; %Dset; return\n", v1);
  			return;
  		}
  		if(debug['C'])
  			print("\n");
  		if(r->s2)
  			constprop(c1, v1, r->s2);
  	}
  }
  
  /*
   * ASLL x,y,w
   * .. (not use w, not set x y w)
   * AXXX w,a,b (a != w)
   * .. (not use w)
   * (set w)
   * ----------- changed to
   * ..
   * AXXX (x<<y),a,b
   * ..
   */
  #define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; }
  int
  shiftprop(Reg *r)
  {
  	Reg *r1;
  	Prog *p, *p1, *p2;
  	int n, o;
  	Adr a;
  
  	p = r->prog;
  	if(p->to.type != D_REG)
  		FAIL("BOTCH: result not reg");
  	n = p->to.reg;
  	a = zprog.from;
  	if(p->reg != NREG && p->reg != p->to.reg) {
  		a.type = D_REG;
  		a.reg = p->reg;
  	}
  	if(debug['H'])
  		print("shiftprop\n%P", p);
  	r1 = r;
  	for(;;) {
  		/* find first use of shift result; abort if shift operands or result are changed */
  		r1 = uniqs(r1);
  		if(r1 == R)
  			FAIL("branch");
  		if(uniqp(r1) == R)
  			FAIL("merge");
  		p1 = r1->prog;
  		if(debug['H'])
  			print("\n%P", p1);
  		switch(copyu(p1, &p->to, A)) {
  		case 0:	/* not used or set */
  			if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) ||
  			   (a.type == D_REG && copyu(p1, &a, A) > 1))
  				FAIL("args modified");
  			continue;
  		case 3:	/* set, not used */
  			FAIL("BOTCH: noref");
  		}
  		break;
  	}
  	/* check whether substitution can be done */
  	switch(p1->as) {
  	default:
  		FAIL("non-dpi");
  	case AAND:
  	case AEOR:
  	case AADD:
  	case AADC:
  	case AORR:
  	case ASUB:
  	case ARSB:
  	case ASBC:
  	case ARSC:
  		if(p1->reg == n || (p1->reg == NREG && p1->to.type == D_REG && p1->to.reg == n)) {
  			if(p1->from.type != D_REG)
  				FAIL("can't swap");
  			p1->reg = p1->from.reg;
  			p1->from.reg = n;
  			switch(p1->as) {
  			case ASUB:
  				p1->as = ARSB;
  				break;
  			case ARSB:
  				p1->as = ASUB;
  				break;
  			case ASBC:
  				p1->as = ARSC;
  				break;
  			case ARSC:
  				p1->as = ASBC;
  				break;
  			}
  			if(debug['H'])
  				print("\t=>%P", p1);
  		}
  	case ABIC:
  	case ACMP:
  	case ACMN:
  		if(p1->reg == n)
  			FAIL("can't swap");
  		if(p1->reg == NREG && p1->to.reg == n)
  			FAIL("shift result used twice");
  	case AMVN:
  		if(p1->from.type == D_SHIFT)
  			FAIL("shift result used in shift");
  		if(p1->from.type != D_REG || p1->from.reg != n)
  			FAIL("BOTCH: where is it used?");
  		break;
  	}
  	/* check whether shift result is used subsequently */
  	p2 = p1;
  	if(p1->to.reg != n)
  	for (;;) {
  		r1 = uniqs(r1);
  		if(r1 == R)
  			FAIL("inconclusive");
  		p1 = r1->prog;
  		if(debug['H'])
  			print("\n%P", p1);
  		switch(copyu(p1, &p->to, A)) {
  		case 0:	/* not used or set */
  			continue;
  		case 3: /* set, not used */
  			break;
  		default:/* used */
  			FAIL("reused");
  		}
  		break;
  	}
  	/* make the substitution */
  	p2->from.type = D_SHIFT;
  	p2->from.reg = NREG;
  	o = p->reg;
  	if(o == NREG)
  		o = p->to.reg;
  	switch(p->from.type){
  	case D_CONST:
  		o |= (p->from.offset&0x1f)<<7;
  		break;
  	case D_REG:
  		o |= (1<<4) | (p->from.reg<<8);
  		break;
  	}
  	switch(p->as){
  	case ASLL:
  		o |= 0<<5;
  		break;
  	case ASRL:
  		o |= 1<<5;
  		break;
  	case ASRA:
  		o |= 2<<5;
  		break;
  	}
  	p2->from.offset = o;
  	if(debug['H'])
  		print("\t=>%P\tSUCCEED\n", p2);
  	return 1;
  }
  
  Reg*
  findpre(Reg *r, Adr *v)
  {
  	Reg *r1;
  
  	for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) {
  		if(uniqs(r1) != r)
  			return R;
  		switch(copyu(r1->prog, v, A)) {
  		case 1: /* used */
  		case 2: /* read-alter-rewrite */
  			return R;
  		case 3: /* set */
  		case 4: /* set and used */
  			return r1;
  		}
  	}
  	return R;
  }
  
  Reg*
  findinc(Reg *r, Reg *r2, Adr *v)
  {
  	Reg *r1;
  	Prog *p;
  
  
  	for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) {
  		if(uniqp(r1) != r)
  			return R;
  		switch(copyu(r1->prog, v, A)) {
  		case 0: /* not touched */
  			continue;
  		case 4: /* set and used */
  			p = r1->prog;
  			if(p->as == AADD)
  			if(p->from.type == D_CONST)
  			if(p->from.offset > -4096 && p->from.offset < 4096)
  				return r1;
  		default:
  			return R;
  		}
  	}
  	return R;
  }
  
  int
  nochange(Reg *r, Reg *r2, Prog *p)
  {
  	Adr a[3];
  	int i, n;
  
  	if(r == r2)
  		return 1;
  	n = 0;
  	if(p->reg != NREG && p->reg != p->to.reg) {
  		a[n].type = D_REG;
  		a[n++].reg = p->reg;
  	}
  	switch(p->from.type) {
  	case D_SHIFT:
  		a[n].type = D_REG;
  		a[n++].reg = p->from.offset&0xf;
  	case D_REG:
  		a[n].type = D_REG;
  		a[n++].reg = p->from.reg;
  	}
  	if(n == 0)
  		return 1;
  	for(; r!=R && r!=r2; r=uniqs(r)) {
  		p = r->prog;
  		for(i=0; i<n; i++)
  			if(copyu(p, &a[i], A) > 1)
  				return 0;
  	}
  	return 1;
  }
  
  int
  findu1(Reg *r, Adr *v)
  {
  	for(; r != R; r = r->s1) {
  		if(r->active)
  			return 0;
  		r->active = 1;
  		switch(copyu(r->prog, v, A)) {
  		case 1: /* used */
  		case 2: /* read-alter-rewrite */
  		case 4: /* set and used */
  			return 1;
  		case 3: /* set */
  			return 0;
  		}
  		if(r->s2)
  			if (findu1(r->s2, v))
  				return 1;
  	}
  	return 0;
  }
  
  int
  finduse(Reg *r, Adr *v)
  {
  	Reg *r1;
  
  	for(r1=firstr; r1!=R; r1=r1->link)
  		r1->active = 0;
  	return findu1(r, v);
  }
  
  int
  xtramodes(Reg *r, Adr *a)
  {
  	Reg *r1, *r2, *r3;
  	Prog *p, *p1;
  	Adr v;
  
  	p = r->prog;
  	if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG)	/* byte load */
  		return 0;
  	v = *a;
  	v.type = D_REG;
  	r1 = findpre(r, &v);
  	if(r1 != R) {
  		p1 = r1->prog;
  		if(p1->to.type == D_REG && p1->to.reg == v.reg)
  		switch(p1->as) {
  		case AADD:
  			if(p1->from.type == D_REG ||
  			   (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
  			    (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
  			   (p1->from.type == D_CONST &&
  			    p1->from.offset > -4096 && p1->from.offset < 4096))
  			if(nochange(uniqs(r1), r, p1)) {
  				if(a != &p->from || v.reg != p->to.reg)
  				if (finduse(r->s1, &v)) {
  					if(p1->reg == NREG || p1->reg == v.reg)
  						/* pre-indexing */
  						p->scond |= C_WBIT;
  					else return 0;
  				}
  				switch (p1->from.type) {
  				case D_REG:
  					/* register offset */
  					a->type = D_SHIFT;
  					a->offset = p1->from.reg;
  					break;
  				case D_SHIFT:
  					/* scaled register offset */
  					a->type = D_SHIFT;
  				case D_CONST:
  					/* immediate offset */
  					a->offset = p1->from.offset;
  					break;
  				}
  				if(p1->reg != NREG)
  					a->reg = p1->reg;
  				excise(r1);
  				return 1;
  			}
  			break;
  		case AMOVW:
  			if(p1->from.type == D_REG)
  			if((r2 = findinc(r1, r, &p1->from)) != R) {
  			for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
  				;
  			if(r3 == r) {
  				/* post-indexing */
  				p1 = r2->prog;
  				a->reg = p1->to.reg;
  				a->offset = p1->from.offset;
  				p->scond |= C_PBIT;
  				if(!finduse(r, &r1->prog->to))
  					excise(r1);
  				excise(r2);
  				return 1;
  			}
  			}
  			break;
  		}
  	}
  	if(a != &p->from || a->reg != p->to.reg)
  	if((r1 = findinc(r, R, &v)) != R) {
  		/* post-indexing */
  		p1 = r1->prog;
  		a->offset = p1->from.offset;
  		p->scond |= C_PBIT;
  		excise(r1);
  		return 1;
  	}
  	return 0;
  }
  
  /*
   * return
   * 1 if v only used (and substitute),
   * 2 if read-alter-rewrite
   * 3 if set
   * 4 if set and used
   * 0 otherwise (not touched)
   */
  int
  copyu(Prog *p, Adr *v, Adr *s)
  {
  
  	switch(p->as) {
  
  	default:
  		if(debug['P'])
  			print(" (?)");
  		return 2;
  
  	case AMOVM:
  		if(v->type != D_REG)
  			return 0;
  		if(p->from.type == D_CONST) {	/* read reglist, read/rar */
  			if(s != A) {
  				if(p->from.offset&(1<<v->reg))
  					return 1;
  				if(copysub(&p->to, v, s, 1))
  					return 1;
  				return 0;
  			}
  			if(copyau(&p->to, v)) {
  				if(p->scond&C_WBIT)
  					return 2;
  				return 1;
  			}
  			if(p->from.offset&(1<<v->reg))
  				return 1;
  		} else {			/* read/rar, write reglist */
  			if(s != A) {
  				if(p->to.offset&(1<<v->reg))
  					return 1;
  				if(copysub(&p->from, v, s, 1))
  					return 1;
  				return 0;
  			}
  			if(copyau(&p->from, v)) {
  				if(p->scond&C_WBIT)
  					return 2;
  				if(p->to.offset&(1<<v->reg))
  					return 4;
  				return 1;
  			}
  			if(p->to.offset&(1<<v->reg))
  				return 3;
  		}
  		return 0;
  
  	case ANOP:	/* read, write */
  	case AMOVW:
  	case AMOVF:
  	case AMOVD:
  	case AMOVH:
  	case AMOVHU:
  	case AMOVB:
  	case AMOVBU:
  	case AMOVDW:
  	case AMOVWD:
  	case AMOVFD:
  	case AMOVDF:
  		if(p->scond&(C_WBIT|C_PBIT))
  		if(v->type == D_REG) {
  			if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
  				if(p->from.reg == v->reg)
  					return 2;
  			} else {
  		  		if(p->to.reg == v->reg)
  				return 2;
  			}
  		}
  		if(s != A) {
  			if(copysub(&p->from, v, s, 1))
  				return 1;
  			if(!copyas(&p->to, v))
  				if(copysub(&p->to, v, s, 1))
  					return 1;
  			return 0;
  		}
  		if(copyas(&p->to, v)) {
  			if(copyau(&p->from, v))
  				return 4;
  			return 3;
  		}
  		if(copyau(&p->from, v))
  			return 1;
  		if(copyau(&p->to, v))
  			return 1;
  		return 0;
  
  
  	case AADD:	/* read, read, write */
  	case ASUB:
  	case ARSB:
  	case ASLL:
  	case ASRL:
  	case ASRA:
  	case AORR:
  	case AAND:
  	case AEOR:
  	case AMUL:
  	case ADIV:
  	case ADIVU:
  	case AADDF:
  	case AADDD:
  	case ASUBF:
  	case ASUBD:
  	case AMULF:
  	case AMULD:
  	case ADIVF:
  	case ADIVD:
  
  	case ACMPF:
  	case ACMPD:
  	case ACMP:
  	case ACMN:
  	case ACASE:
  		if(s != A) {
  			if(copysub(&p->from, v, s, 1))
  				return 1;
  			if(copysub1(p, v, s, 1))
  				return 1;
  			if(!copyas(&p->to, v))
  				if(copysub(&p->to, v, s, 1))
  					return 1;
  			return 0;
  		}
  		if(copyas(&p->to, v)) {
  			if(p->reg == NREG)
  				p->reg = p->to.reg;
  			if(copyau(&p->from, v))
  				return 4;
  			if(copyau1(p, v))
  				return 4;
  			return 3;
  		}
  		if(copyau(&p->from, v))
  			return 1;
  		if(copyau1(p, v))
  			return 1;
  		if(copyau(&p->to, v))
  			return 1;
  		return 0;
  
  	case ABEQ:	/* read, read */
  	case ABNE:
  	case ABCS:
  	case ABHS:
  	case ABCC:
  	case ABLO:
  	case ABMI:
  	case ABPL:
  	case ABVS:
  	case ABVC:
  	case ABHI:
  	case ABLS:
  	case ABGE:
  	case ABLT:
  	case ABGT:
  	case ABLE:
  	case APLD:
  		if(s != A) {
  			if(copysub(&p->from, v, s, 1))
  				return 1;
  			return copysub1(p, v, s, 1);
  		}
  		if(copyau(&p->from, v))
  			return 1;
  		if(copyau1(p, v))
  			return 1;
  		return 0;
  
  	case AB:	/* funny */
  		if(s != A) {
  			if(copysub(&p->to, v, s, 1))
  				return 1;
  			return 0;
  		}
  		if(copyau(&p->to, v))
  			return 1;
  		return 0;
  
  	case ARET:	/* funny */
  		if(v->type == D_REG)
  		if(v->reg == REGRET)
  			return 2;
  		if(v->type == D_FREG)
  		if(v->reg == FREGRET)
  			return 2;
  
  	case ABL:	/* funny */
  		if(v->type == D_REG) {
  			if(v->reg <= REGEXT && v->reg > exregoffset)
  				return 2;
  			if(v->reg == (uchar)REGARG)
  				return 2;
  		}
  		if(v->type == D_FREG)
  			if(v->reg <= FREGEXT && v->reg > exfregoffset)
  				return 2;
  
  		if(s != A) {
  			if(copysub(&p->to, v, s, 1))
  				return 1;
  			return 0;
  		}
  		if(copyau(&p->to, v))
  			return 4;
  		return 3;
  
  	case ATEXT:	/* funny */
  		if(v->type == D_REG)
  			if(v->reg == (uchar)REGARG)
  				return 3;
  		return 0;
  	}
  }
  
  int
  a2type(Prog *p)
  {
  
  	switch(p->as) {
  
  	case ACMP:
  	case ACMN:
  
  	case AADD:
  	case ASUB:
  	case ARSB:
  	case ASLL:
  	case ASRL:
  	case ASRA:
  	case AORR:
  	case AAND:
  	case AEOR:
  	case AMUL:
  	case ADIV:
  	case ADIVU:
  		return D_REG;
  
  	case ACMPF:
  	case ACMPD:
  
  	case AADDF:
  	case AADDD:
  	case ASUBF:
  	case ASUBD:
  	case AMULF:
  	case AMULD:
  	case ADIVF:
  	case ADIVD:
  		return D_FREG;
  	}
  	return D_NONE;
  }
  
  /*
   * direct reference,
   * could be set/use depending on
   * semantics
   */
  int
  copyas(Adr *a, Adr *v)
  {
  
  	if(regtyp(v)) {
  		if(a->type == v->type)
  		if(a->reg == v->reg)
  			return 1;
  	} else if(v->type == D_CONST) {		/* for constprop */
  		if(a->type == v->type)
  		if(a->name == v->name)
  		if(a->sym == v->sym)
  		if(a->reg == v->reg)
  		if(a->offset == v->offset)
  			return 1;
  	}
  	return 0;
  }
  
  /*
   * either direct or indirect
   */
  int
  copyau(Adr *a, Adr *v)
  {
  
  	if(copyas(a, v))
  		return 1;
  	if(v->type == D_REG) {
  		if(a->type == D_OREG) {
  			if(v->reg == a->reg)
  				return 1;
  		} else if(a->type == D_SHIFT) {
  			if((a->offset&0xf) == v->reg)
  				return 1;
  			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
  				return 1;
  		}
  	}
  	return 0;
  }
  
  int
  copyau1(Prog *p, Adr *v)
  {
  
  	if(regtyp(v)) {
  		if(a2type(p) == v->type)
  		if(p->reg == v->reg) {
  			if(a2type(p) != v->type)
  				print("botch a2type %P\n", p);
  			return 1;
  		}
  	}
  	return 0;
  }
  
  /*
   * substitute s for v in a
   * return failure to substitute
   */
  int
  copysub(Adr *a, Adr *v, Adr *s, int f)
  {
  
  	if(f)
  	if(copyau(a, v)) {
  		if(a->type == D_SHIFT) {
  			if((a->offset&0xf) == v->reg)
  				a->offset = (a->offset&~0xf)|s->reg;
  			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
  				a->offset = (a->offset&~(0xf<<8))|(s->reg<<8);
  		} else
  			a->reg = s->reg;
  	}
  	return 0;
  }
  
  int
  copysub1(Prog *p1, Adr *v, Adr *s, int f)
  {
  
  	if(f)
  	if(copyau1(p1, v))
  		p1->reg = s->reg;
  	return 0;
  }
  
  struct {
  	int opcode;
  	int notopcode;
  	int scond;
  	int notscond;
  } predinfo[]  = {
  	{ ABEQ,	ABNE,	0x0,	0x1, },
  	{ ABNE,	ABEQ,	0x1,	0x0, },
  	{ ABCS,	ABCC,	0x2,	0x3, },
  	{ ABHS,	ABLO,	0x2,	0x3, },
  	{ ABCC,	ABCS,	0x3,	0x2, },
  	{ ABLO,	ABHS,	0x3,	0x2, },
  	{ ABMI,	ABPL,	0x4,	0x5, },
  	{ ABPL,	ABMI,	0x5,	0x4, },
  	{ ABVS,	ABVC,	0x6,	0x7, },
  	{ ABVC,	ABVS,	0x7,	0x6, },
  	{ ABHI,	ABLS,	0x8,	0x9, },
  	{ ABLS,	ABHI,	0x9,	0x8, },
  	{ ABGE,	ABLT,	0xA,	0xB, },
  	{ ABLT,	ABGE,	0xB,	0xA, },
  	{ ABGT,	ABLE,	0xC,	0xD, },
  	{ ABLE,	ABGT,	0xD,	0xC, },
  };
  
  typedef struct {
  	Reg *start;
  	Reg *last;
  	Reg *end;
  	int len;
  } Joininfo;
  
  enum {
  	Join,
  	Split,
  	End,
  	Branch,
  	Setcond,
  	Toolong
  };
  
  enum {
  	Falsecond,
  	Truecond,
  	Delbranch,
  	Keepbranch
  };
  
  int
  isbranch(Prog *p)
  {
  	return (ABEQ <= p->as) && (p->as <= ABLE);
  }
  
  int
  predicable(Prog *p)
  {
  	if (isbranch(p)
  		|| p->as == ANOP
  		|| p->as == AXXX
  		|| p->as == ADATA
  		|| p->as == AGLOBL
  		|| p->as == AGOK
  		|| p->as == AHISTORY
  		|| p->as == ANAME
  		|| p->as == ASIGNAME
  		|| p->as == ATEXT
  		|| p->as == AWORD
  		|| p->as == ABCASE
  		|| p->as == ACASE)
  		return 0;
  	return 1;
  }
  
  /*
   * Depends on an analysis of the encodings performed by 5l.
   * These seem to be all of the opcodes that lead to the "S" bit
   * being set in the instruction encodings.
   *
   * C_SBIT may also have been set explicitly in p->scond.
   */
  int
  modifiescpsr(Prog *p)
  {
  	return (p->scond&C_SBIT)
  		|| p->as == ATST
  		|| p->as == ATEQ
  		|| p->as == ACMN
  		|| p->as == ACMP
  		|| p->as == AMULU
  		|| p->as == ADIVU
  		|| p->as == AMUL
  		|| p->as == ADIV
  		|| p->as == AMOD
  		|| p->as == AMODU
  		|| p->as == ABL;
  }
  
  /*
   * Find the maximal chain of instructions starting with r which could
   * be executed conditionally
   */
  int
  joinsplit(Reg *r, Joininfo *j)
  {
  	j->start = r;
  	j->last = r;
  	j->len = 0;
  	do {
  		if (r->p2 && (r->p1 || r->p2->p2link)) {
  			j->end = r;
  			return Join;
  		}
  		if (r->s1 && r->s2) {
  			j->end = r;
  			return Split;
  		}
  		j->last = r;
  		if (r->prog->as != ANOP)
  			j->len++;
  		if (!r->s1 && !r->s2) {
  			j->end = r->link;
  			return End;
  		}
  		if (r->s2) {
  			j->end = r->s2;
  			return Branch;
  		}
  		if (modifiescpsr(r->prog)) {
  			j->end = r->s1;
  			return Setcond;
  		}
  		r = r->s1;
  	} while (j->len < 4);
  	j->end = r;
  	return Toolong;
  }
  
  Reg *
  successor(Reg *r)
  {
  	if (r->s1)
  		return r->s1;
  	else
  		return r->s2;
  }
  
  void
  applypred(Reg *rstart, Joininfo *j, int cond, int branch)
  {
  	int pred;
  	Reg *r;
  
  	if(j->len == 0)
  		return;
  	if (cond == Truecond)
  		pred = predinfo[rstart->prog->as - ABEQ].scond;
  	else
  		pred = predinfo[rstart->prog->as - ABEQ].notscond;
  
  	for (r = j->start; ; r = successor(r)) {
  		if (r->prog->as == AB) {
  			if (r != j->last || branch == Delbranch)
  				excise(r);
  			else {
  			  if (cond == Truecond)
  				r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
  			  else
  				r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
  			}
  		}
  		else if (predicable(r->prog))
  			r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
  		if (r->s1 != r->link) {
  			r->s1 = r->link;
  			r->link->p1 = r;
  		}
  		if (r == j->last)
  			break;
  	}
  }
  
  void
  predicate(void)
  {
  	Reg *r;
  	int t1, t2;
  	Joininfo j1, j2;
  
  	for(r=firstr; r!=R; r=r->link) {
  		if (isbranch(r->prog)) {
  			t1 = joinsplit(r->s1, &j1);
  			t2 = joinsplit(r->s2, &j2);
  			if(j1.last->link != j2.start)
  				continue;
  			if(j1.end == j2.end)
  			if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
  			   (t2 == Join && (t1 == Join || t1 == Setcond))) {
  				applypred(r, &j1, Falsecond, Delbranch);
  				applypred(r, &j2, Truecond, Delbranch);
  				excise(r);
  				continue;
  			}
  			if(t1 == End || t1 == Branch) {
  				applypred(r, &j1, Falsecond, Keepbranch);
  				excise(r);
  				continue;
  			}
  		}
  	}
  }
  