reg.c 28.3 KB
Newer Older
Ken Thompson's avatar
Ken Thompson committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
// Derived from Inferno utils/6c/reg.c
// http://code.google.com/p/inferno-os/source/browse/utils/6c/reg.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.

Russ Cox's avatar
Russ Cox committed
31 32
#include <u.h>
#include <libc.h>
Ken Thompson's avatar
Ken Thompson committed
33 34 35
#include "gg.h"
#include "opt.h"

36 37
#define	NREGVAR	32	/* 16 general + 16 floating */
#define	REGBITS	((uint32)0xffffffff)
Ken Thompson's avatar
Ken Thompson committed
38 39
#define	P2R(p)	(Reg*)(p->reg)

40
static	int	first	= 1;
Ken Thompson's avatar
Ken Thompson committed
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

Reg*
rega(void)
{
	Reg *r;

	r = freer;
	if(r == R) {
		r = mal(sizeof(*r));
	} else
		freer = r->link;

	*r = zreg;
	return r;
}

int
rcmp(const void *a1, const void *a2)
{
	Rgn *p1, *p2;
	int c1, c2;

	p1 = (Rgn*)a1;
	p2 = (Rgn*)a2;
	c1 = p2->cost;
	c2 = p1->cost;
	if(c1 -= c2)
		return c1;
	return p2->varno - p1->varno;
}

Ken Thompson's avatar
Ken Thompson committed
72
static void
Ken Thompson's avatar
Ken Thompson committed
73 74 75 76 77 78 79 80 81 82 83 84 85
setoutvar(void)
{
	Type *t;
	Node *n;
	Addr a;
	Iter save;
	Bits bit;
	int z;

	t = structfirst(&save, getoutarg(curfn->type));
	while(t != T) {
		n = nodarg(t, 1);
		a = zprog.from;
Russ Cox's avatar
Russ Cox committed
86
		naddr(n, &a, 0);
Ken Thompson's avatar
Ken Thompson committed
87 88 89 90 91 92 93 94 95
		bit = mkvar(R, &a);
		for(z=0; z<BITS; z++)
			ovar.b[z] |= bit.b[z];
		t = structnext(&save);
	}
//if(bany(b))
//print("ovars = %Q\n", &ovar);
}

Ken Thompson's avatar
Ken Thompson committed
96 97 98
static void
setaddrs(Bits bit)
{
Ken Thompson's avatar
Ken Thompson committed
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
	int i, n;
	Var *v;
	Sym *s;

	while(bany(&bit)) {
		// convert each bit to a variable
		i = bnum(bit);
		s = var[i].sym;
		n = var[i].name;
		bit.b[i/32] &= ~(1L<<(i%32));

		// disable all pieces of that variable
		for(i=0; i<nvar; i++) {
			v = var+i;
			if(v->sym == s && v->name == n)
				v->addr = 2;
		}
	}
Ken Thompson's avatar
Ken Thompson committed
117 118
}

119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
static char* regname[] = {
	".AX",
	".CX",
	".DX",
	".BX",
	".SP",
	".BP",
	".SI",
	".DI",
	".R8",
	".R9",
	".R10",
	".R11",
	".R12",
	".R13",
	".R14",
	".R15",
	".X0",
	".X1",
	".X2",
	".X3",
	".X4",
	".X5",
	".X6",
	".X7",
	".X8",
	".X9",
	".X10",
	".X11",
	".X12",
	".X13",
	".X14",
	".X15",
};

Ken Thompson's avatar
Ken Thompson committed
154 155 156
void
regopt(Prog *firstp)
{
157 158
	Reg *r, *r1;
	Prog *p;
Ken Thompson's avatar
Ken Thompson committed
159 160 161 162 163 164
	int i, z, nr;
	uint32 vreg;
	Bits bit;

	if(first) {
		fmtinstall('Q', Qconv);
Ken Thompson's avatar
Ken Thompson committed
165
		exregoffset = D_R13;	// R14,R15 are external
Ken Thompson's avatar
Ken Thompson committed
166 167 168
		first = 0;
	}

169 170 171 172 173 174
	// count instructions
	nr = 0;
	for(p=firstp; p!=P; p=p->link)
		nr++;
	// if too big dont bother
	if(nr >= 10000) {
Ken Thompson's avatar
Ken Thompson committed
175
//		print("********** %S is too big (%d)\n", curfn->nname->sym, nr);
176 177 178
		return;
	}

Russ Cox's avatar
Russ Cox committed
179
	r1 = R;
Ken Thompson's avatar
Ken Thompson committed
180 181
	firstr = R;
	lastr = R;
182 183 184 185 186 187 188 189 190 191 192

	/*
	 * control flow is more complicated in generated go code
	 * than in generated c code.  define pseudo-variables for
	 * registers, so we have complete register usage information.
	 */
	nvar = NREGVAR;
	memset(var, 0, NREGVAR*sizeof var[0]);
	for(i=0; i<NREGVAR; i++)
		var[i].sym = lookup(regname[i]);

Ken Thompson's avatar
Ken Thompson committed
193 194 195 196 197 198
	regbits = RtoB(D_SP);
	for(z=0; z<BITS; z++) {
		externs.b[z] = 0;
		params.b[z] = 0;
		consts.b[z] = 0;
		addrs.b[z] = 0;
Ken Thompson's avatar
Ken Thompson committed
199
		ovar.b[z] = 0;
Ken Thompson's avatar
Ken Thompson committed
200 201
	}

Ken Thompson's avatar
Ken Thompson committed
202 203 204
	// build list of return variables
	setoutvar();

Ken Thompson's avatar
Ken Thompson committed
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
	/*
	 * pass 1
	 * build aux data structure
	 * allocate pcs
	 * find use and set of variables
	 */
	nr = 0;
	for(p=firstp; p!=P; p=p->link) {
		switch(p->as) {
		case ADATA:
		case AGLOBL:
		case ANAME:
		case ASIGNAME:
			continue;
		}
		r = rega();
		nr++;
		if(firstr == R) {
			firstr = r;
			lastr = r;
		} else {
			lastr->link = r;
			r->p1 = lastr;
			lastr->s1 = r;
			lastr = r;
		}
		r->prog = p;
		p->reg = r;

		r1 = r->p1;
		if(r1 != R) {
			switch(r1->prog->as) {
			case ARET:
			case AJMP:
			case AIRETL:
			case AIRETQ:
				r->p1 = R;
				r1->s1 = R;
			}
		}

		bit = mkvar(r, &p->from);
		if(bany(&bit))
		switch(p->as) {
		/*
		 * funny
		 */
		case ALEAL:
		case ALEAQ:
Ken Thompson's avatar
Ken Thompson committed
254
			setaddrs(bit);
Ken Thompson's avatar
Ken Thompson committed
255 256 257 258 259 260 261 262 263
			break;

		/*
		 * left side read
		 */
		default:
			for(z=0; z<BITS; z++)
				r->use1.b[z] |= bit.b[z];
			break;
Russ Cox's avatar
Russ Cox committed
264 265 266 267 268 269 270 271 272 273 274 275 276

		/*
		 * left side read+write
		 */
		case AXCHGB:
		case AXCHGW:
		case AXCHGL:
		case AXCHGQ:
			for(z=0; z<BITS; z++) {
				r->use1.b[z] |= bit.b[z];
				r->set.b[z] |= bit.b[z];
			}
			break;
Ken Thompson's avatar
Ken Thompson committed
277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
		}

		bit = mkvar(r, &p->to);
		if(bany(&bit))
		switch(p->as) {
		default:
			yyerror("reg: unknown op: %A", p->as);
			break;

		/*
		 * right side read
		 */
		case ACMPB:
		case ACMPL:
		case ACMPQ:
		case ACMPW:
		case ACOMISS:
		case ACOMISD:
		case AUCOMISS:
		case AUCOMISD:
297 298 299
		case ATESTB:
		case ATESTL:
		case ATESTQ:
Ken Thompson's avatar
Ken Thompson committed
300 301 302 303 304 305 306
			for(z=0; z<BITS; z++)
				r->use2.b[z] |= bit.b[z];
			break;

		/*
		 * right side write
		 */
307
		case ALEAQ:
Ken Thompson's avatar
Ken Thompson committed
308 309 310 311 312 313 314
		case ANOP:
		case AMOVL:
		case AMOVQ:
		case AMOVB:
		case AMOVW:
		case AMOVBLSX:
		case AMOVBLZX:
315 316
		case AMOVBWSX:
		case AMOVBWZX:
Ken Thompson's avatar
Ken Thompson committed
317 318 319 320 321 322 323 324
		case AMOVBQSX:
		case AMOVBQZX:
		case AMOVLQSX:
		case AMOVLQZX:
		case AMOVWLSX:
		case AMOVWLZX:
		case AMOVWQSX:
		case AMOVWQZX:
325
		case APOPQ:
Ken Thompson's avatar
Ken Thompson committed
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349

		case AMOVSS:
		case AMOVSD:
		case ACVTSD2SL:
		case ACVTSD2SQ:
		case ACVTSD2SS:
		case ACVTSL2SD:
		case ACVTSL2SS:
		case ACVTSQ2SD:
		case ACVTSQ2SS:
		case ACVTSS2SD:
		case ACVTSS2SL:
		case ACVTSS2SQ:
		case ACVTTSD2SL:
		case ACVTTSD2SQ:
		case ACVTTSS2SL:
		case ACVTTSS2SQ:
			for(z=0; z<BITS; z++)
				r->set.b[z] |= bit.b[z];
			break;

		/*
		 * right side read+write
		 */
Ken Thompson's avatar
Ken Thompson committed
350 351 352 353 354 355 356 357 358
		case AINCB:
		case AINCL:
		case AINCQ:
		case AINCW:
		case ADECB:
		case ADECL:
		case ADECQ:
		case ADECW:

Ken Thompson's avatar
Ken Thompson committed
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
		case AADDB:
		case AADDL:
		case AADDQ:
		case AADDW:
		case AANDB:
		case AANDL:
		case AANDQ:
		case AANDW:
		case ASUBB:
		case ASUBL:
		case ASUBQ:
		case ASUBW:
		case AORB:
		case AORL:
		case AORQ:
		case AORW:
		case AXORB:
		case AXORL:
		case AXORQ:
		case AXORW:
		case ASALB:
		case ASALL:
		case ASALQ:
		case ASALW:
		case ASARB:
		case ASARL:
		case ASARQ:
		case ASARW:
387 388 389 390 391 392 393 394
		case ARCLB:
		case ARCLL:
		case ARCLQ:
		case ARCLW:
		case ARCRB:
		case ARCRL:
		case ARCRQ:
		case ARCRW:
Ken Thompson's avatar
Ken Thompson committed
395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413
		case AROLB:
		case AROLL:
		case AROLQ:
		case AROLW:
		case ARORB:
		case ARORL:
		case ARORQ:
		case ARORW:
		case ASHLB:
		case ASHLL:
		case ASHLQ:
		case ASHLW:
		case ASHRB:
		case ASHRL:
		case ASHRQ:
		case ASHRW:
		case AIMULL:
		case AIMULQ:
		case AIMULW:
414 415
		case ANEGB:
		case ANEGW:
Ken Thompson's avatar
Ken Thompson committed
416 417 418 419 420 421 422 423 424
		case ANEGL:
		case ANEGQ:
		case ANOTL:
		case ANOTQ:
		case AADCL:
		case AADCQ:
		case ASBBL:
		case ASBBQ:

425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
		case ASETCC:
		case ASETCS:
		case ASETEQ:
		case ASETGE:
		case ASETGT:
		case ASETHI:
		case ASETLE:
		case ASETLS:
		case ASETLT:
		case ASETMI:
		case ASETNE:
		case ASETOC:
		case ASETOS:
		case ASETPC:
		case ASETPL:
		case ASETPS:

Russ Cox's avatar
Russ Cox committed
442 443 444 445 446
		case AXCHGB:
		case AXCHGW:
		case AXCHGL:
		case AXCHGQ:

Ken Thompson's avatar
Ken Thompson committed
447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
		case AADDSD:
		case AADDSS:
		case ACMPSD:
		case ACMPSS:
		case ADIVSD:
		case ADIVSS:
		case AMAXSD:
		case AMAXSS:
		case AMINSD:
		case AMINSS:
		case AMULSD:
		case AMULSS:
		case ARCPSS:
		case ARSQRTSS:
		case ASQRTSD:
		case ASQRTSS:
		case ASUBSD:
		case ASUBSS:
		case AXORPD:
			for(z=0; z<BITS; z++) {
				r->set.b[z] |= bit.b[z];
				r->use2.b[z] |= bit.b[z];
			}
			break;

		/*
		 * funny
		 */
		case ACALL:
Ken Thompson's avatar
Ken Thompson committed
476
			setaddrs(bit);
Ken Thompson's avatar
Ken Thompson committed
477 478 479 480 481 482 483 484 485 486 487 488
			break;
		}

		switch(p->as) {
		case AIMULL:
		case AIMULQ:
		case AIMULW:
			if(p->to.type != D_NONE)
				break;

		case AIDIVL:
		case AIDIVW:
489
		case AIDIVQ:
Ken Thompson's avatar
Ken Thompson committed
490 491
		case ADIVL:
		case ADIVW:
492
		case ADIVQ:
Ken Thompson's avatar
Ken Thompson committed
493 494
		case AMULL:
		case AMULW:
495 496 497 498 499 500 501 502 503 504 505 506
		case AMULQ:
			r->set.b[0] |= RtoB(D_AX) | RtoB(D_DX);
			r->use1.b[0] |= RtoB(D_AX) | RtoB(D_DX);
			break;

		case AIDIVB:
		case AIMULB:
		case ADIVB:
 		case AMULB:
			r->set.b[0] |= RtoB(D_AX);
			r->use1.b[0] |= RtoB(D_AX);
			break;
Ken Thompson's avatar
Ken Thompson committed
507 508

		case ACWD:
509 510
			r->set.b[0] |= RtoB(D_AX) | RtoB(D_DX);
			r->use1.b[0] |= RtoB(D_AX);
Ken Thompson's avatar
Ken Thompson committed
511 512
			break;

513 514 515 516 517
		case ACDQ:
			r->set.b[0] |= RtoB(D_DX);
			r->use1.b[0] |= RtoB(D_AX);
 			break;

Ken Thompson's avatar
Ken Thompson committed
518 519 520 521 522
		case AREP:
		case AREPN:
		case ALOOP:
		case ALOOPEQ:
		case ALOOPNE:
523 524
			r->set.b[0] |= RtoB(D_CX);
			r->use1.b[0] |= RtoB(D_CX);
Ken Thompson's avatar
Ken Thompson committed
525 526 527 528 529 530 531 532 533 534
			break;

		case AMOVSB:
		case AMOVSL:
		case AMOVSQ:
		case AMOVSW:
		case ACMPSB:
		case ACMPSL:
		case ACMPSQ:
		case ACMPSW:
535 536
			r->set.b[0] |= RtoB(D_SI) | RtoB(D_DI);
			r->use1.b[0] |= RtoB(D_SI) | RtoB(D_DI);
Ken Thompson's avatar
Ken Thompson committed
537 538 539 540 541 542 543 544 545 546
			break;

		case ASTOSB:
		case ASTOSL:
		case ASTOSQ:
		case ASTOSW:
		case ASCASB:
		case ASCASL:
		case ASCASQ:
		case ASCASW:
547 548
			r->set.b[0] |= RtoB(D_DI);
			r->use1.b[0] |= RtoB(D_AX) | RtoB(D_DI);
Ken Thompson's avatar
Ken Thompson committed
549 550 551 552 553
			break;

		case AINSB:
		case AINSL:
		case AINSW:
554 555 556 557
			r->set.b[0] |= RtoB(D_DX) | RtoB(D_DI);
			r->use1.b[0] |= RtoB(D_DI);
			break;

Ken Thompson's avatar
Ken Thompson committed
558 559 560
		case AOUTSB:
		case AOUTSL:
		case AOUTSW:
561 562
			r->set.b[0] |= RtoB(D_DI);
			r->use1.b[0] |= RtoB(D_DX) | RtoB(D_DI);
Ken Thompson's avatar
Ken Thompson committed
563 564 565 566 567
			break;
		}
	}
	if(firstr == R)
		return;
Ken Thompson's avatar
Ken Thompson committed
568

Ken Thompson's avatar
Ken Thompson committed
569 570 571 572 573 574 575 576 577 578 579 580
	for(i=0; i<nvar; i++) {
		Var *v = var+i;
		if(v->addr) {
			bit = blsh(i);
			for(z=0; z<BITS; z++)
				addrs.b[z] |= bit.b[z];
		}

//		print("bit=%2d addr=%d et=%-6E w=%-2d s=%S + %lld\n",
//			i, v->addr, v->etype, v->width, v->sym, v->offset);
	}

Ken Thompson's avatar
Ken Thompson committed
581 582
	if(debug['R'] && debug['v'])
		dumpit("pass1", firstr);
Ken Thompson's avatar
Ken Thompson committed
583 584 585 586 587 588 589 590 591 592 593 594 595 596 597

	/*
	 * pass 2
	 * turn branch references to pointers
	 * build back pointers
	 */
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		if(p->to.type == D_BRANCH) {
			if(p->to.branch == P)
				fatal("pnil %P", p);
			r1 = p->to.branch->reg;
			if(r1 == R)
				fatal("rnil %P", p);
			if(r1 == r) {
Ken Thompson's avatar
Ken Thompson committed
598
				//fatal("ref to self %P", p);
Ken Thompson's avatar
Ken Thompson committed
599 600 601 602 603 604 605
				continue;
			}
			r->s2 = r1;
			r->p2link = r1->p2;
			r1->p2 = r;
		}
	}
Ken Thompson's avatar
Ken Thompson committed
606 607 608

	if(debug['R'] && debug['v'])
		dumpit("pass2", firstr);
Ken Thompson's avatar
Ken Thompson committed
609 610 611 612 613 614 615 616 617

	/*
	 * pass 2.5
	 * find looping structure
	 */
	for(r = firstr; r != R; r = r->link)
		r->active = 0;
	change = 0;
	loopit(firstr, nr);
Ken Thompson's avatar
Ken Thompson committed
618 619 620

	if(debug['R'] && debug['v'])
		dumpit("pass2.5", firstr);
Ken Thompson's avatar
Ken Thompson committed
621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648

	/*
	 * pass 3
	 * iterate propagating usage
	 * 	back until flow graph is complete
	 */
loop1:
	change = 0;
	for(r = firstr; r != R; r = r->link)
		r->active = 0;
	for(r = firstr; r != R; r = r->link)
		if(r->prog->as == ARET)
			prop(r, zbits, zbits);
loop11:
	/* pick up unreachable code */
	i = 0;
	for(r = firstr; r != R; r = r1) {
		r1 = r->link;
		if(r1 && r1->active && !r->active) {
			prop(r, zbits, zbits);
			i = 1;
		}
	}
	if(i)
		goto loop11;
	if(change)
		goto loop1;

Ken Thompson's avatar
Ken Thompson committed
649 650
	if(debug['R'] && debug['v'])
		dumpit("pass3", firstr);
Ken Thompson's avatar
Ken Thompson committed
651 652 653 654 655 656 657 658 659 660 661 662 663 664

	/*
	 * pass 4
	 * iterate propagating register/variable synchrony
	 * 	forward until graph is complete
	 */
loop2:
	change = 0;
	for(r = firstr; r != R; r = r->link)
		r->active = 0;
	synch(firstr, zbits);
	if(change)
		goto loop2;

Ken Thompson's avatar
Ken Thompson committed
665 666
	if(debug['R'] && debug['v'])
		dumpit("pass4", firstr);
Ken Thompson's avatar
Ken Thompson committed
667

668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685
	/*
	 * pass 4.5
	 * move register pseudo-variables into regu.
	 */
	for(r = firstr; r != R; r = r->link) {
		r->regu = (r->refbehind.b[0] | r->set.b[0]) & REGBITS;

		r->set.b[0] &= ~REGBITS;
		r->use1.b[0] &= ~REGBITS;
		r->use2.b[0] &= ~REGBITS;
		r->refbehind.b[0] &= ~REGBITS;
		r->refahead.b[0] &= ~REGBITS;
		r->calbehind.b[0] &= ~REGBITS;
		r->calahead.b[0] &= ~REGBITS;
		r->regdiff.b[0] &= ~REGBITS;
		r->act.b[0] &= ~REGBITS;
	}

Ken Thompson's avatar
Ken Thompson committed
686 687 688 689 690 691 692 693 694 695
	/*
	 * pass 5
	 * isolate regions
	 * calculate costs (paint1)
	 */
	r = firstr;
	if(r) {
		for(z=0; z<BITS; z++)
			bit.b[z] = (r->refahead.b[z] | r->calahead.b[z]) &
			  ~(externs.b[z] | params.b[z] | addrs.b[z] | consts.b[z]);
Ken Thompson's avatar
Ken Thompson committed
696 697 698 699 700
		if(bany(&bit) && !r->refset) {
			// should never happen - all variables are preset
			if(debug['w'])
				print("%L: used and not set: %Q\n", r->prog->lineno, bit);
			r->refset = 1;
Ken Thompson's avatar
Ken Thompson committed
701 702 703 704 705 706 707 708 709 710
		}
	}
	for(r = firstr; r != R; r = r->link)
		r->act = zbits;
	rgp = region;
	nregion = 0;
	for(r = firstr; r != R; r = r->link) {
		for(z=0; z<BITS; z++)
			bit.b[z] = r->set.b[z] &
			  ~(r->refahead.b[z] | r->calahead.b[z] | addrs.b[z]);
Ken Thompson's avatar
Ken Thompson committed
711 712 713 714
		if(bany(&bit) && !r->refset) {
			if(debug['w'])
				print("%L: set and not used: %Q\n", r->prog->lineno, bit);
			r->refset = 1;
Ken Thompson's avatar
Ken Thompson committed
715 716 717 718 719 720 721 722 723 724 725
			excise(r);
		}
		for(z=0; z<BITS; z++)
			bit.b[z] = LOAD(r) & ~(r->act.b[z] | addrs.b[z]);
		while(bany(&bit)) {
			i = bnum(bit);
			rgp->enter = r;
			rgp->varno = i;
			change = 0;
			paint1(r, i);
			bit.b[i/32] &= ~(1L<<(i%32));
Ken Thompson's avatar
Ken Thompson committed
726
			if(change <= 0)
Ken Thompson's avatar
Ken Thompson committed
727 728 729 730
				continue;
			rgp->cost = change;
			nregion++;
			if(nregion >= NRGN) {
Ken Thompson's avatar
Ken Thompson committed
731 732
				if(debug['R'] && debug['v'])
					print("too many regions\n");
Ken Thompson's avatar
Ken Thompson committed
733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
				goto brk;
			}
			rgp++;
		}
	}
brk:
	qsort(region, nregion, sizeof(region[0]), rcmp);

	/*
	 * pass 6
	 * determine used registers (paint2)
	 * replace code (paint3)
	 */
	rgp = region;
	for(i=0; i<nregion; i++) {
		bit = blsh(rgp->varno);
		vreg = paint2(rgp->enter, rgp->varno);
		vreg = allreg(vreg, rgp);
		if(rgp->regno != 0)
			paint3(rgp->enter, rgp->varno, vreg, rgp->regno);
		rgp++;
	}

Ken Thompson's avatar
Ken Thompson committed
756 757 758
	if(debug['R'] && debug['v'])
		dumpit("pass6", firstr);

Ken Thompson's avatar
Ken Thompson committed
759 760 761 762
	/*
	 * pass 7
	 * peep-hole on basic block
	 */
Ken Thompson's avatar
Ken Thompson committed
763
	if(!debug['R'] || debug['P']) {
Ken Thompson's avatar
Ken Thompson committed
764 765 766 767 768 769 770 771
		peep();
	}

	/*
	 * eliminate nops
	 * free aux structures
	 */
	for(p=firstp; p!=P; p=p->link) {
Ken Thompson's avatar
Ken Thompson committed
772
		while(p->link != P && p->link->as == ANOP)
Ken Thompson's avatar
Ken Thompson committed
773
			p->link = p->link->link;
Ken Thompson's avatar
Ken Thompson committed
774 775 776
		if(p->to.type == D_BRANCH)
			while(p->to.branch != P && p->to.branch->as == ANOP)
				p->to.branch = p->to.branch->link;
Ken Thompson's avatar
Ken Thompson committed
777 778 779 780 781 782
	}

	if(r1 != R) {
		r1->link = freer;
		freer = firstr;
	}
Ken Thompson's avatar
Ken Thompson committed
783 784 785 786 787 788 789 790 791 792 793 794

	if(debug['R']) {
		if(ostats.ncvtreg ||
		   ostats.nspill ||
		   ostats.nreload ||
		   ostats.ndelmov ||
		   ostats.nvar ||
		   ostats.naddr ||
		   0)
			print("\nstats\n");

		if(ostats.ncvtreg)
Russ Cox's avatar
Russ Cox committed
795
			print("	%4d cvtreg\n", ostats.ncvtreg);
Ken Thompson's avatar
Ken Thompson committed
796
		if(ostats.nspill)
Russ Cox's avatar
Russ Cox committed
797
			print("	%4d spill\n", ostats.nspill);
Ken Thompson's avatar
Ken Thompson committed
798
		if(ostats.nreload)
Russ Cox's avatar
Russ Cox committed
799
			print("	%4d reload\n", ostats.nreload);
Ken Thompson's avatar
Ken Thompson committed
800
		if(ostats.ndelmov)
Russ Cox's avatar
Russ Cox committed
801
			print("	%4d delmov\n", ostats.ndelmov);
Ken Thompson's avatar
Ken Thompson committed
802
		if(ostats.nvar)
Russ Cox's avatar
Russ Cox committed
803
			print("	%4d delmov\n", ostats.nvar);
Ken Thompson's avatar
Ken Thompson committed
804
		if(ostats.naddr)
Russ Cox's avatar
Russ Cox committed
805
			print("	%4d delmov\n", ostats.naddr);
Ken Thompson's avatar
Ken Thompson committed
806 807 808

		memset(&ostats, 0, sizeof(ostats));
	}
Ken Thompson's avatar
Ken Thompson committed
809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837
}

/*
 * add mov b,rn
 * just after r
 */
void
addmove(Reg *r, int bn, int rn, int f)
{
	Prog *p, *p1;
	Adr *a;
	Var *v;

	p1 = mal(sizeof(*p1));
	clearp(p1);
	p1->loc = 9999;

	p = r->prog;
	p1->link = p->link;
	p->link = p1;
	p1->lineno = p->lineno;

	v = var + bn;

	a = &p1->to;
	a->sym = v->sym;
	a->offset = v->offset;
	a->etype = v->etype;
	a->type = v->name;
Russ Cox's avatar
Russ Cox committed
838
	a->gotype = v->gotype;
Luuk van Dijk's avatar
Luuk van Dijk committed
839
	a->node = v->node;
Ken Thompson's avatar
Ken Thompson committed
840

Ken Thompson's avatar
Ken Thompson committed
841
	// need to clean this up with wptr and
Ken Thompson's avatar
Ken Thompson committed
842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865
	// some of the defaults
	p1->as = AMOVL;
	switch(v->etype) {
	default:
		fatal("unknown type\n");
	case TINT8:
	case TUINT8:
	case TBOOL:
		p1->as = AMOVB;
		break;
	case TINT16:
	case TUINT16:
		p1->as = AMOVW;
		break;
	case TINT64:
	case TUINT64:
	case TUINTPTR:
	case TPTR64:
		p1->as = AMOVQ;
		break;
	case TFLOAT32:
		p1->as = AMOVSS;
		break;
	case TFLOAT64:
Ken Thompson's avatar
Ken Thompson committed
866
		p1->as = AMOVSD;
Ken Thompson's avatar
Ken Thompson committed
867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885
		break;
	case TINT:
	case TUINT:
	case TINT32:
	case TUINT32:
	case TPTR32:
		break;
	}

	p1->from.type = rn;
	if(!f) {
		p1->from = *a;
		*a = zprog.from;
		a->type = rn;
		if(v->etype == TUINT8)
			p1->as = AMOVB;
		if(v->etype == TUINT16)
			p1->as = AMOVW;
	}
Ken Thompson's avatar
Ken Thompson committed
886 887 888
	if(debug['R'] && debug['v'])
		print("%P ===add=== %P\n", p, p1);
	ostats.nspill++;
Ken Thompson's avatar
Ken Thompson committed
889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912
}

uint32
doregbits(int r)
{
	uint32 b;

	b = 0;
	if(r >= D_INDIR)
		r -= D_INDIR;
	if(r >= D_AX && r <= D_R15)
		b |= RtoB(r);
	else
	if(r >= D_AL && r <= D_R15B)
		b |= RtoB(r-D_AL+D_AX);
	else
	if(r >= D_AH && r <= D_BH)
		b |= RtoB(r-D_AH+D_AX);
	else
	if(r >= D_X0 && r <= D_X0+15)
		b |= FtoB(r);
	return b;
}

913
static int
Ken Thompson's avatar
Ken Thompson committed
914
overlap(int32 o1, int w1, int32 o2, int w2)
915
{
Ken Thompson's avatar
Ken Thompson committed
916
	int32 t1, t2;
917 918 919

	t1 = o1+w1;
	t2 = o2+w2;
Ken Thompson's avatar
Ken Thompson committed
920

921 922 923 924 925 926
	if(!(t1 > o2 && t2 > o1))
		return 0;

	return 1;
}

Ken Thompson's avatar
Ken Thompson committed
927 928 929 930
Bits
mkvar(Reg *r, Adr *a)
{
	Var *v;
931
	int i, t, n, et, z, w, flag;
932
	uint32 regu;
Ken Thompson's avatar
Ken Thompson committed
933 934 935 936 937 938 939 940
	int32 o;
	Bits bit;
	Sym *s;

	/*
	 * mark registers used
	 */
	t = a->type;
Ken Thompson's avatar
Ken Thompson committed
941 942 943
	if(t == D_NONE)
		goto none;

944 945
	if(r != R)
		r->use1.b[0] |= doregbits(a->index);
Ken Thompson's avatar
Ken Thompson committed
946 947 948

	switch(t) {
	default:
949 950 951 952 953 954
		regu = doregbits(t);
		if(regu == 0)
			goto none;
		bit = zbits;
		bit.b[0] = regu;
		return bit;
Ken Thompson's avatar
Ken Thompson committed
955

Ken Thompson's avatar
Ken Thompson committed
956 957 958
	case D_ADDR:
		a->type = a->index;
		bit = mkvar(r, a);
Ken Thompson's avatar
Ken Thompson committed
959
		setaddrs(bit);
Ken Thompson's avatar
Ken Thompson committed
960
		a->type = t;
Ken Thompson's avatar
Ken Thompson committed
961
		ostats.naddr++;
Ken Thompson's avatar
Ken Thompson committed
962
		goto none;
Ken Thompson's avatar
Ken Thompson committed
963

Ken Thompson's avatar
Ken Thompson committed
964 965 966 967 968 969 970 971 972 973
	case D_EXTERN:
	case D_STATIC:
	case D_PARAM:
	case D_AUTO:
		n = t;
		break;
	}
	s = a->sym;
	if(s == S)
		goto none;
974
	if(s->name[0] == '.')
975
		goto none;
Ken Thompson's avatar
Ken Thompson committed
976 977
	et = a->etype;
	o = a->offset;
978
	w = a->width;
979 980

	flag = 0;
Ken Thompson's avatar
Ken Thompson committed
981
	for(i=0; i<nvar; i++) {
Ken Thompson's avatar
Ken Thompson committed
982 983
		v = var+i;
		if(v->sym == s && v->name == n) {
Ken Thompson's avatar
Ken Thompson committed
984 985 986
			if(v->offset == o)
			if(v->etype == et)
			if(v->width == w)
Ken Thompson's avatar
Ken Thompson committed
987 988
				return blsh(i);

Ken Thompson's avatar
Ken Thompson committed
989
			// if they overlaps, disable both
Ken Thompson's avatar
Ken Thompson committed
990
			if(overlap(v->offset, v->width, o, w)) {
991
//				print("disable overlap %s %d %d %d %d, %E != %E\n", s->name, v->offset, v->width, o, w, v->etype, et);
Ken Thompson's avatar
Ken Thompson committed
992
				v->addr = 1;
993
				flag = 1;
Ken Thompson's avatar
Ken Thompson committed
994
			}
995
		}
Ken Thompson's avatar
Ken Thompson committed
996
	}
997 998
	if(a->pun) {
//		print("disable pun %s\n", s->name);
Ken Thompson's avatar
Ken Thompson committed
999
		flag = 1;
Ken Thompson's avatar
Ken Thompson committed
1000

1001
	}
Ken Thompson's avatar
Ken Thompson committed
1002
	switch(et) {
1003
	case 0:
Ken Thompson's avatar
Ken Thompson committed
1004 1005 1006 1007 1008 1009
	case TFUNC:
		goto none;
	}

	if(nvar >= NVAR) {
		if(debug['w'] > 1 && s)
1010
			fatal("variable not optimized: %D", a);
Ken Thompson's avatar
Ken Thompson committed
1011 1012
		goto none;
	}
Ken Thompson's avatar
Ken Thompson committed
1013

Ken Thompson's avatar
Ken Thompson committed
1014 1015
	i = nvar;
	nvar++;
Ken Thompson's avatar
Ken Thompson committed
1016
	v = var+i;
Ken Thompson's avatar
Ken Thompson committed
1017 1018 1019
	v->sym = s;
	v->offset = o;
	v->name = n;
Russ Cox's avatar
Russ Cox committed
1020
	v->gotype = a->gotype;
Ken Thompson's avatar
Ken Thompson committed
1021
	v->etype = et;
1022
	v->width = w;
Ken Thompson's avatar
Ken Thompson committed
1023
	v->addr = flag;		// funny punning
Luuk van Dijk's avatar
Luuk van Dijk committed
1024
	v->node = a->node;
Ken Thompson's avatar
Ken Thompson committed
1025

Ken Thompson's avatar
Ken Thompson committed
1026
	if(debug['R'])
Ken Thompson's avatar
Ken Thompson committed
1027
		print("bit=%2d et=%2d w=%d %S %D\n", i, et, w, s, a);
Ken Thompson's avatar
Ken Thompson committed
1028
	ostats.nvar++;
Ken Thompson's avatar
Ken Thompson committed
1029 1030

	bit = blsh(i);
1031 1032 1033 1034 1035 1036 1037
	if(n == D_EXTERN || n == D_STATIC)
		for(z=0; z<BITS; z++)
			externs.b[z] |= bit.b[z];
	if(n == D_PARAM)
		for(z=0; z<BITS; z++)
			params.b[z] |= bit.b[z];

Ken Thompson's avatar
Ken Thompson committed
1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081
	return bit;

none:
	return zbits;
}

void
prop(Reg *r, Bits ref, Bits cal)
{
	Reg *r1, *r2;
	int z;

	for(r1 = r; r1 != R; r1 = r1->p1) {
		for(z=0; z<BITS; z++) {
			ref.b[z] |= r1->refahead.b[z];
			if(ref.b[z] != r1->refahead.b[z]) {
				r1->refahead.b[z] = ref.b[z];
				change++;
			}
			cal.b[z] |= r1->calahead.b[z];
			if(cal.b[z] != r1->calahead.b[z]) {
				r1->calahead.b[z] = cal.b[z];
				change++;
			}
		}
		switch(r1->prog->as) {
		case ACALL:
			if(noreturn(r1->prog))
				break;
			for(z=0; z<BITS; z++) {
				cal.b[z] |= ref.b[z] | externs.b[z];
				ref.b[z] = 0;
			}
			break;

		case ATEXT:
			for(z=0; z<BITS; z++) {
				cal.b[z] = 0;
				ref.b[z] = 0;
			}
			break;

		case ARET:
			for(z=0; z<BITS; z++) {
Ken Thompson's avatar
Ken Thompson committed
1082
				cal.b[z] = externs.b[z] | ovar.b[z];
Ken Thompson's avatar
Ken Thompson committed
1083 1084
				ref.b[z] = 0;
			}
Ken Thompson's avatar
Ken Thompson committed
1085
			break;
Ken Thompson's avatar
Ken Thompson committed
1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274
		}
		for(z=0; z<BITS; z++) {
			ref.b[z] = (ref.b[z] & ~r1->set.b[z]) |
				r1->use1.b[z] | r1->use2.b[z];
			cal.b[z] &= ~(r1->set.b[z] | r1->use1.b[z] | r1->use2.b[z]);
			r1->refbehind.b[z] = ref.b[z];
			r1->calbehind.b[z] = cal.b[z];
		}
		if(r1->active)
			break;
		r1->active = 1;
	}
	for(; r != r1; r = r->p1)
		for(r2 = r->p2; r2 != R; r2 = r2->p2link)
			prop(r2, r->refbehind, r->calbehind);
}

/*
 * find looping structure
 *
 * 1) find reverse postordering
 * 2) find approximate dominators,
 *	the actual dominators if the flow graph is reducible
 *	otherwise, dominators plus some other non-dominators.
 *	See Matthew S. Hecht and Jeffrey D. Ullman,
 *	"Analysis of a Simple Algorithm for Global Data Flow Problems",
 *	Conf.  Record of ACM Symp. on Principles of Prog. Langs, Boston, Massachusetts,
 *	Oct. 1-3, 1973, pp.  207-217.
 * 3) find all nodes with a predecessor dominated by the current node.
 *	such a node is a loop head.
 *	recursively, all preds with a greater rpo number are in the loop
 */
int32
postorder(Reg *r, Reg **rpo2r, int32 n)
{
	Reg *r1;

	r->rpo = 1;
	r1 = r->s1;
	if(r1 && !r1->rpo)
		n = postorder(r1, rpo2r, n);
	r1 = r->s2;
	if(r1 && !r1->rpo)
		n = postorder(r1, rpo2r, n);
	rpo2r[n] = r;
	n++;
	return n;
}

int32
rpolca(int32 *idom, int32 rpo1, int32 rpo2)
{
	int32 t;

	if(rpo1 == -1)
		return rpo2;
	while(rpo1 != rpo2){
		if(rpo1 > rpo2){
			t = rpo2;
			rpo2 = rpo1;
			rpo1 = t;
		}
		while(rpo1 < rpo2){
			t = idom[rpo2];
			if(t >= rpo2)
				fatal("bad idom");
			rpo2 = t;
		}
	}
	return rpo1;
}

int
doms(int32 *idom, int32 r, int32 s)
{
	while(s > r)
		s = idom[s];
	return s == r;
}

int
loophead(int32 *idom, Reg *r)
{
	int32 src;

	src = r->rpo;
	if(r->p1 != R && doms(idom, src, r->p1->rpo))
		return 1;
	for(r = r->p2; r != R; r = r->p2link)
		if(doms(idom, src, r->rpo))
			return 1;
	return 0;
}

void
loopmark(Reg **rpo2r, int32 head, Reg *r)
{
	if(r->rpo < head || r->active == head)
		return;
	r->active = head;
	r->loop += LOOP;
	if(r->p1 != R)
		loopmark(rpo2r, head, r->p1);
	for(r = r->p2; r != R; r = r->p2link)
		loopmark(rpo2r, head, r);
}

void
loopit(Reg *r, int32 nr)
{
	Reg *r1;
	int32 i, d, me;

	if(nr > maxnr) {
		rpo2r = mal(nr * sizeof(Reg*));
		idom = mal(nr * sizeof(int32));
		maxnr = nr;
	}

	d = postorder(r, rpo2r, 0);
	if(d > nr)
		fatal("too many reg nodes %d %d", d, nr);
	nr = d;
	for(i = 0; i < nr / 2; i++) {
		r1 = rpo2r[i];
		rpo2r[i] = rpo2r[nr - 1 - i];
		rpo2r[nr - 1 - i] = r1;
	}
	for(i = 0; i < nr; i++)
		rpo2r[i]->rpo = i;

	idom[0] = 0;
	for(i = 0; i < nr; i++) {
		r1 = rpo2r[i];
		me = r1->rpo;
		d = -1;
		if(r1->p1 != R && r1->p1->rpo < me)
			d = r1->p1->rpo;
		for(r1 = r1->p2; r1 != nil; r1 = r1->p2link)
			if(r1->rpo < me)
				d = rpolca(idom, d, r1->rpo);
		idom[i] = d;
	}

	for(i = 0; i < nr; i++) {
		r1 = rpo2r[i];
		r1->loop++;
		if(r1->p2 != R && loophead(idom, r1))
			loopmark(rpo2r, i, r1);
	}
}

void
synch(Reg *r, Bits dif)
{
	Reg *r1;
	int z;

	for(r1 = r; r1 != R; r1 = r1->s1) {
		for(z=0; z<BITS; z++) {
			dif.b[z] = (dif.b[z] &
				~(~r1->refbehind.b[z] & r1->refahead.b[z])) |
					r1->set.b[z] | r1->regdiff.b[z];
			if(dif.b[z] != r1->regdiff.b[z]) {
				r1->regdiff.b[z] = dif.b[z];
				change++;
			}
		}
		if(r1->active)
			break;
		r1->active = 1;
		for(z=0; z<BITS; z++)
			dif.b[z] &= ~(~r1->calbehind.b[z] & r1->calahead.b[z]);
		if(r1->s2 != R)
			synch(r1->s2, dif);
	}
}

uint32
allreg(uint32 b, Rgn *r)
{
	Var *v;
	int i;

	v = var + r->varno;
	r->regno = 0;
	switch(v->etype) {

	default:
Ken Thompson's avatar
Ken Thompson committed
1275
		fatal("unknown etype %d/%E", bitno(b), v->etype);
Ken Thompson's avatar
Ken Thompson committed
1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385
		break;

	case TINT8:
	case TUINT8:
	case TINT16:
	case TUINT16:
	case TINT32:
	case TUINT32:
	case TINT64:
	case TUINT64:
	case TINT:
	case TUINT:
	case TUINTPTR:
	case TBOOL:
	case TPTR32:
	case TPTR64:
		i = BtoR(~b);
		if(i && r->cost > 0) {
			r->regno = i;
			return RtoB(i);
		}
		break;

	case TFLOAT32:
	case TFLOAT64:
		i = BtoF(~b);
		if(i && r->cost > 0) {
			r->regno = i;
			return FtoB(i);
		}
		break;
	}
	return 0;
}

void
paint1(Reg *r, int bn)
{
	Reg *r1;
	int z;
	uint32 bb;

	z = bn/32;
	bb = 1L<<(bn%32);
	if(r->act.b[z] & bb)
		return;
	for(;;) {
		if(!(r->refbehind.b[z] & bb))
			break;
		r1 = r->p1;
		if(r1 == R)
			break;
		if(!(r1->refahead.b[z] & bb))
			break;
		if(r1->act.b[z] & bb)
			break;
		r = r1;
	}

	if(LOAD(r) & ~(r->set.b[z]&~(r->use1.b[z]|r->use2.b[z])) & bb) {
		change -= CLOAD * r->loop;
	}
	for(;;) {
		r->act.b[z] |= bb;

		if(r->use1.b[z] & bb) {
			change += CREF * r->loop;
		}

		if((r->use2.b[z]|r->set.b[z]) & bb) {
			change += CREF * r->loop;
		}

		if(STORE(r) & r->regdiff.b[z] & bb) {
			change -= CLOAD * r->loop;
		}

		if(r->refbehind.b[z] & bb)
			for(r1 = r->p2; r1 != R; r1 = r1->p2link)
				if(r1->refahead.b[z] & bb)
					paint1(r1, bn);

		if(!(r->refahead.b[z] & bb))
			break;
		r1 = r->s2;
		if(r1 != R)
			if(r1->refbehind.b[z] & bb)
				paint1(r1, bn);
		r = r->s1;
		if(r == R)
			break;
		if(r->act.b[z] & bb)
			break;
		if(!(r->refbehind.b[z] & bb))
			break;
	}
}

uint32
regset(Reg *r, uint32 bb)
{
	uint32 b, set;
	Adr v;
	int c;

	set = 0;
	v = zprog.from;
	while(b = bb & ~(bb-1)) {
		v.type = b & 0xFFFF? BtoR(b): BtoF(b);
		if(v.type == 0)
Russ Cox's avatar
Russ Cox committed
1386
			fatal("zero v.type for %#ux", b);
Ken Thompson's avatar
Ken Thompson committed
1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505
		c = copyu(r->prog, &v, A);
		if(c == 3)
			set |= b;
		bb &= ~b;
	}
	return set;
}

uint32
reguse(Reg *r, uint32 bb)
{
	uint32 b, set;
	Adr v;
	int c;

	set = 0;
	v = zprog.from;
	while(b = bb & ~(bb-1)) {
		v.type = b & 0xFFFF? BtoR(b): BtoF(b);
		c = copyu(r->prog, &v, A);
		if(c == 1 || c == 2 || c == 4)
			set |= b;
		bb &= ~b;
	}
	return set;
}

uint32
paint2(Reg *r, int bn)
{
	Reg *r1;
	int z;
	uint32 bb, vreg, x;

	z = bn/32;
	bb = 1L << (bn%32);
	vreg = regbits;
	if(!(r->act.b[z] & bb))
		return vreg;
	for(;;) {
		if(!(r->refbehind.b[z] & bb))
			break;
		r1 = r->p1;
		if(r1 == R)
			break;
		if(!(r1->refahead.b[z] & bb))
			break;
		if(!(r1->act.b[z] & bb))
			break;
		r = r1;
	}
	for(;;) {
		r->act.b[z] &= ~bb;

		vreg |= r->regu;

		if(r->refbehind.b[z] & bb)
			for(r1 = r->p2; r1 != R; r1 = r1->p2link)
				if(r1->refahead.b[z] & bb)
					vreg |= paint2(r1, bn);

		if(!(r->refahead.b[z] & bb))
			break;
		r1 = r->s2;
		if(r1 != R)
			if(r1->refbehind.b[z] & bb)
				vreg |= paint2(r1, bn);
		r = r->s1;
		if(r == R)
			break;
		if(!(r->act.b[z] & bb))
			break;
		if(!(r->refbehind.b[z] & bb))
			break;
	}

	bb = vreg;
	for(; r; r=r->s1) {
		x = r->regu & ~bb;
		if(x) {
			vreg |= reguse(r, x);
			bb |= regset(r, x);
		}
	}
	return vreg;
}

void
paint3(Reg *r, int bn, int32 rb, int rn)
{
	Reg *r1;
	Prog *p;
	int z;
	uint32 bb;

	z = bn/32;
	bb = 1L << (bn%32);
	if(r->act.b[z] & bb)
		return;
	for(;;) {
		if(!(r->refbehind.b[z] & bb))
			break;
		r1 = r->p1;
		if(r1 == R)
			break;
		if(!(r1->refahead.b[z] & bb))
			break;
		if(r1->act.b[z] & bb)
			break;
		r = r1;
	}

	if(LOAD(r) & ~(r->set.b[z] & ~(r->use1.b[z]|r->use2.b[z])) & bb)
		addmove(r, bn, rn, 0);
	for(;;) {
		r->act.b[z] |= bb;
		p = r->prog;

		if(r->use1.b[z] & bb) {
Ken Thompson's avatar
Ken Thompson committed
1506
			if(debug['R'] && debug['v'])
Ken Thompson's avatar
Ken Thompson committed
1507 1508
				print("%P", p);
			addreg(&p->from, rn);
Ken Thompson's avatar
Ken Thompson committed
1509 1510
			if(debug['R'] && debug['v'])
				print(" ===change== %P\n", p);
Ken Thompson's avatar
Ken Thompson committed
1511 1512
		}
		if((r->use2.b[z]|r->set.b[z]) & bb) {
Ken Thompson's avatar
Ken Thompson committed
1513
			if(debug['R'] && debug['v'])
Ken Thompson's avatar
Ken Thompson committed
1514 1515
				print("%P", p);
			addreg(&p->to, rn);
Ken Thompson's avatar
Ken Thompson committed
1516 1517
			if(debug['R'] && debug['v'])
				print(" ===change== %P\n", p);
Ken Thompson's avatar
Ken Thompson committed
1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551
		}

		if(STORE(r) & r->regdiff.b[z] & bb)
			addmove(r, bn, rn, 1);
		r->regu |= rb;

		if(r->refbehind.b[z] & bb)
			for(r1 = r->p2; r1 != R; r1 = r1->p2link)
				if(r1->refahead.b[z] & bb)
					paint3(r1, bn, rb, rn);

		if(!(r->refahead.b[z] & bb))
			break;
		r1 = r->s2;
		if(r1 != R)
			if(r1->refbehind.b[z] & bb)
				paint3(r1, bn, rb, rn);
		r = r->s1;
		if(r == R)
			break;
		if(r->act.b[z] & bb)
			break;
		if(!(r->refbehind.b[z] & bb))
			break;
	}
}

void
addreg(Adr *a, int rn)
{

	a->sym = 0;
	a->offset = 0;
	a->type = rn;
Ken Thompson's avatar
Ken Thompson committed
1552 1553

	ostats.ncvtreg++;
Ken Thompson's avatar
Ken Thompson committed
1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567
}

int32
RtoB(int r)
{

	if(r < D_AX || r > D_R15)
		return 0;
	return 1L << (r-D_AX);
}

int
BtoR(int32 b)
{
Ken Thompson's avatar
Ken Thompson committed
1568
	b &= 0x3fffL;		// no R14 or R15
Ken Thompson's avatar
Ken Thompson committed
1569 1570 1571 1572 1573 1574 1575
	if(b == 0)
		return 0;
	return bitno(b) + D_AX;
}

/*
 *	bit	reg
1576 1577 1578
 *	16	X5 (FREGMIN)
 *	...
 *	26	X15 (FREGEXT)
Ken Thompson's avatar
Ken Thompson committed
1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591
 */
int32
FtoB(int f)
{
	if(f < FREGMIN || f > FREGEXT)
		return 0;
	return 1L << (f - FREGMIN + 16);
}

int
BtoF(int32 b)
{

1592
	b &= 0xFF0000L;
Ken Thompson's avatar
Ken Thompson committed
1593 1594 1595 1596 1597
	if(b == 0)
		return 0;
	return bitno(b) - 16 + FREGMIN;
}

Ken Thompson's avatar
Ken Thompson committed
1598
void
1599
dumpone(Reg *r)
Ken Thompson's avatar
Ken Thompson committed
1600 1601 1602 1603
{
	int z;
	Bits bit;

Russ Cox's avatar
Russ Cox committed
1604
	print("%d:%P", r->loop, r->prog);
1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645
	for(z=0; z<BITS; z++)
		bit.b[z] =
			r->set.b[z] |
			r->use1.b[z] |
			r->use2.b[z] |
			r->refbehind.b[z] |
			r->refahead.b[z] |
			r->calbehind.b[z] |
			r->calahead.b[z] |
			r->regdiff.b[z] |
			r->act.b[z] |
				0;
	if(bany(&bit)) {
		print("\t");
		if(bany(&r->set))
			print(" s:%Q", r->set);
		if(bany(&r->use1))
			print(" u1:%Q", r->use1);
		if(bany(&r->use2))
			print(" u2:%Q", r->use2);
		if(bany(&r->refbehind))
			print(" rb:%Q ", r->refbehind);
		if(bany(&r->refahead))
			print(" ra:%Q ", r->refahead);
		if(bany(&r->calbehind))
			print("cb:%Q ", r->calbehind);
		if(bany(&r->calahead))
			print(" ca:%Q ", r->calahead);
		if(bany(&r->regdiff))
			print(" d:%Q ", r->regdiff);
		if(bany(&r->act))
			print(" a:%Q ", r->act);
	}
	print("\n");
}

void
dumpit(char *str, Reg *r0)
{
	Reg *r, *r1;

Ken Thompson's avatar
Ken Thompson committed
1646 1647
	print("\n%s\n", str);
	for(r = r0; r != R; r = r->link) {
1648
		dumpone(r);
Ken Thompson's avatar
Ken Thompson committed
1649 1650 1651 1652
		r1 = r->p2;
		if(r1 != R) {
			print("	pred:");
			for(; r1 != R; r1 = r1->p2link)
Russ Cox's avatar
Russ Cox committed
1653
				print(" %.4ud", r1->prog->loc);
Ken Thompson's avatar
Ken Thompson committed
1654 1655 1656 1657 1658 1659
			print("\n");
		}
//		r1 = r->s1;
//		if(r1 != R) {
//			print("	succ:");
//			for(; r1 != R; r1 = r1->s1)
Russ Cox's avatar
Russ Cox committed
1660
//				print(" %.4ud", r1->prog->loc);
Ken Thompson's avatar
Ken Thompson committed
1661 1662 1663 1664 1665 1666 1667
//			print("\n");
//		}
	}
}

static Sym*	symlist[10];

Ken Thompson's avatar
Ken Thompson committed
1668
int
Ken Thompson's avatar
Ken Thompson committed
1669 1670 1671 1672 1673 1674
noreturn(Prog *p)
{
	Sym *s;
	int i;

	if(symlist[0] == S) {
1675 1676
		symlist[0] = pkglookup("panicindex", runtimepkg);
		symlist[1] = pkglookup("panicslice", runtimepkg);
1677
		symlist[2] = pkglookup("throwinit", runtimepkg);
1678
		symlist[3] = pkglookup("panic", runtimepkg);
1679
		symlist[4] = pkglookup("panicwrap", runtimepkg);
Ken Thompson's avatar
Ken Thompson committed
1680 1681 1682 1683 1684 1685 1686 1687 1688 1689
	}

	s = p->to.sym;
	if(s == S)
		return 0;
	for(i=0; symlist[i]!=S; i++)
		if(s == symlist[i])
			return 1;
	return 0;
}