peep.c 19.1 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/peep.c
// http://code.google.com/p/inferno-os/source/browse/utils/6c/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.

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

36 37 38 39 40 41 42 43 44 45 46
static void	conprop(Flow *r);
static void	elimshortmov(Graph *g);
static int	prevl(Flow *r, int reg);
static void	pushback(Flow *r);
static int	regconsttyp(Adr*);
static int	subprop(Flow*);
static int	copyprop(Graph*, Flow*);
static int	copy1(Adr*, Adr*, Flow*, int);
static int	copyas(Adr*, Adr*);
static int	copyau(Adr*, Adr*);
static int	copysub(Adr*, Adr*, Adr*, int);
47
static int	copyu(Prog*, Adr*, Adr*);
Ken Thompson's avatar
Ken Thompson committed
48

49 50
static uint32	gactive;

51 52 53 54 55
enum
{
	exregoffset = REG_R15,
};

Ken Thompson's avatar
Ken Thompson committed
56
// do we need the carry bit
Ken Thompson's avatar
Ken Thompson committed
57 58 59
static int
needc(Prog *p)
{
60 61
	ProgInfo info;

Ken Thompson's avatar
Ken Thompson committed
62
	while(p != P) {
63 64
		proginfo(&info, p);
		if(info.flags & UseCarry)
Ken Thompson's avatar
Ken Thompson committed
65
			return 1;
66
		if(info.flags & (SetCarry|KillCarry))
Ken Thompson's avatar
Ken Thompson committed
67 68 69 70 71 72
			return 0;
		p = p->link;
	}
	return 0;
}

73 74
static Flow*
rnops(Flow *r)
Ken Thompson's avatar
Ken Thompson committed
75 76
{
	Prog *p;
77
	Flow *r1;
Ken Thompson's avatar
Ken Thompson committed
78

79
	if(r != nil)
Ken Thompson's avatar
Ken Thompson committed
80
	for(;;) {
Ken Thompson's avatar
Ken Thompson committed
81
		p = r->prog;
82
		if(p->as != ANOP || p->from.type != TYPE_NONE || p->to.type != TYPE_NONE)
Ken Thompson's avatar
Ken Thompson committed
83 84
			break;
		r1 = uniqs(r);
85
		if(r1 == nil)
Ken Thompson's avatar
Ken Thompson committed
86 87 88 89 90 91 92
			break;
		r = r1;
	}
	return r;
}

void
93
peep(Prog *firstp)
Ken Thompson's avatar
Ken Thompson committed
94
{
95 96
	Flow *r, *r1;
	Graph *g;
Ken Thompson's avatar
Ken Thompson committed
97 98 99
	Prog *p, *p1;
	int t;

100
	g = flowstart(firstp, 0);
101 102
	if(g == nil)
		return;
103
	gactive = 0;
Ken Thompson's avatar
Ken Thompson committed
104

105
	// byte, word arithmetic elimination.
106
	elimshortmov(g);
107

Ken Thompson's avatar
Ken Thompson committed
108
	// constant propagation
109 110 111
	// find MOV $con,R followed by
	// another MOV $con,R without
	// setting R in the interim
112
	for(r=g->start; r!=nil; r=r->link) {
Ken Thompson's avatar
Ken Thompson committed
113 114 115 116 117
		p = r->prog;
		switch(p->as) {
		case ALEAL:
		case ALEAQ:
			if(regtyp(&p->to))
118
			if(p->from.sym != nil)
119
			if(p->from.index == REG_NONE)
Ken Thompson's avatar
Ken Thompson committed
120 121 122 123 124 125 126 127 128 129
				conprop(r);
			break;

		case AMOVB:
		case AMOVW:
		case AMOVL:
		case AMOVQ:
		case AMOVSS:
		case AMOVSD:
			if(regtyp(&p->to))
130
			if(p->from.type == TYPE_CONST || p->from.type == TYPE_FCONST)
Ken Thompson's avatar
Ken Thompson committed
131 132 133 134
				conprop(r);
			break;
		}
	}
Ken Thompson's avatar
Ken Thompson committed
135

Ken Thompson's avatar
Ken Thompson committed
136
loop1:
Ken Thompson's avatar
Ken Thompson committed
137
	if(debug['P'] && debug['v'])
138
		dumpit("loop1", g->start, 0);
Ken Thompson's avatar
Ken Thompson committed
139

Ken Thompson's avatar
Ken Thompson committed
140
	t = 0;
141
	for(r=g->start; r!=nil; r=r->link) {
Ken Thompson's avatar
Ken Thompson committed
142 143 144 145 146 147 148 149
		p = r->prog;
		switch(p->as) {
		case AMOVL:
		case AMOVQ:
		case AMOVSS:
		case AMOVSD:
			if(regtyp(&p->to))
			if(regtyp(&p->from)) {
150
				if(copyprop(g, r)) {
Ken Thompson's avatar
Ken Thompson committed
151 152 153
					excise(r);
					t++;
				} else
154
				if(subprop(r) && copyprop(g, r)) {
Ken Thompson's avatar
Ken Thompson committed
155 156 157 158 159 160 161 162 163 164 165 166
					excise(r);
					t++;
				}
			}
			break;

		case AMOVBLZX:
		case AMOVWLZX:
		case AMOVBLSX:
		case AMOVWLSX:
			if(regtyp(&p->to)) {
				r1 = rnops(uniqs(r));
167
				if(r1 != nil) {
Ken Thompson's avatar
Ken Thompson committed
168
					p1 = r1->prog;
169
					if(p->as == p1->as && p->to.type == p1->from.type && p->to.reg == p1->from.reg){
Ken Thompson's avatar
Ken Thompson committed
170 171 172 173 174 175 176 177 178 179 180 181 182
						p1->as = AMOVL;
						t++;
					}
				}
			}
			break;

		case AMOVBQSX:
		case AMOVBQZX:
		case AMOVWQSX:
		case AMOVWQZX:
		case AMOVLQSX:
		case AMOVLQZX:
183
		case AMOVQL:
Ken Thompson's avatar
Ken Thompson committed
184 185
			if(regtyp(&p->to)) {
				r1 = rnops(uniqs(r));
186
				if(r1 != nil) {
Ken Thompson's avatar
Ken Thompson committed
187
					p1 = r1->prog;
188
					if(p->as == p1->as && p->to.type == p1->from.type && p->to.reg == p1->from.reg){
Ken Thompson's avatar
Ken Thompson committed
189 190 191 192 193 194 195 196 197 198
						p1->as = AMOVQ;
						t++;
					}
				}
			}
			break;

		case AADDL:
		case AADDQ:
		case AADDW:
199
			if(p->from.type != TYPE_CONST || needc(p->link))
Ken Thompson's avatar
Ken Thompson committed
200 201 202 203
				break;
			if(p->from.offset == -1){
				if(p->as == AADDQ)
					p->as = ADECQ;
Ken Thompson's avatar
Ken Thompson committed
204 205
				else
				if(p->as == AADDL)
Ken Thompson's avatar
Ken Thompson committed
206 207 208 209
					p->as = ADECL;
				else
					p->as = ADECW;
				p->from = zprog.from;
Ken Thompson's avatar
Ken Thompson committed
210
				break;
Ken Thompson's avatar
Ken Thompson committed
211
			}
Ken Thompson's avatar
Ken Thompson committed
212
			if(p->from.offset == 1){
Ken Thompson's avatar
Ken Thompson committed
213 214 215 216 217 218 219
				if(p->as == AADDQ)
					p->as = AINCQ;
				else if(p->as == AADDL)
					p->as = AINCL;
				else
					p->as = AINCW;
				p->from = zprog.from;
Ken Thompson's avatar
Ken Thompson committed
220
				break;
Ken Thompson's avatar
Ken Thompson committed
221 222 223 224 225 226
			}
			break;

		case ASUBL:
		case ASUBQ:
		case ASUBW:
227
			if(p->from.type != TYPE_CONST || needc(p->link))
Ken Thompson's avatar
Ken Thompson committed
228 229 230 231
				break;
			if(p->from.offset == -1) {
				if(p->as == ASUBQ)
					p->as = AINCQ;
Ken Thompson's avatar
Ken Thompson committed
232 233
				else
				if(p->as == ASUBL)
Ken Thompson's avatar
Ken Thompson committed
234 235 236 237
					p->as = AINCL;
				else
					p->as = AINCW;
				p->from = zprog.from;
Ken Thompson's avatar
Ken Thompson committed
238
				break;
Ken Thompson's avatar
Ken Thompson committed
239
			}
Ken Thompson's avatar
Ken Thompson committed
240
			if(p->from.offset == 1){
Ken Thompson's avatar
Ken Thompson committed
241 242
				if(p->as == ASUBQ)
					p->as = ADECQ;
Ken Thompson's avatar
Ken Thompson committed
243 244
				else
				if(p->as == ASUBL)
Ken Thompson's avatar
Ken Thompson committed
245 246 247 248
					p->as = ADECL;
				else
					p->as = ADECW;
				p->from = zprog.from;
Ken Thompson's avatar
Ken Thompson committed
249
				break;
Ken Thompson's avatar
Ken Thompson committed
250 251 252 253 254 255
			}
			break;
		}
	}
	if(t)
		goto loop1;
Russ Cox's avatar
Russ Cox committed
256 257 258 259 260 261 262

	// MOVLQZX removal.
	// The MOVLQZX exists to avoid being confused for a
	// MOVL that is just copying 32-bit data around during
	// copyprop.  Now that copyprop is done, remov MOVLQZX R1, R2
	// if it is dominated by an earlier ADDL/MOVL/etc into R1 that
	// will have already cleared the high bits.
263 264 265 266 267 268
	//
	// MOVSD removal.
	// We never use packed registers, so a MOVSD between registers
	// can be replaced by MOVAPD, which moves the pair of float64s
	// instead of just the lower one.  We only use the lower one, but
	// the processor can do better if we do moves using both.
269
	for(r=g->start; r!=nil; r=r->link) {
Russ Cox's avatar
Russ Cox committed
270 271 272
		p = r->prog;
		if(p->as == AMOVLQZX)
		if(regtyp(&p->from))
273 274
		if(p->from.type == p->to.type && p->from.reg == p->to.reg)
		if(prevl(r, p->from.reg))
Russ Cox's avatar
Russ Cox committed
275
			excise(r);
276 277 278 279 280
		
		if(p->as == AMOVSD)
		if(regtyp(&p->from))
		if(regtyp(&p->to))
			p->as = AMOVAPD;
Russ Cox's avatar
Russ Cox committed
281 282 283 284 285
	}

	// load pipelining
	// push any load from memory as early as possible
	// to give it time to complete before use.
286
	for(r=g->start; r!=nil; r=r->link) {
Russ Cox's avatar
Russ Cox committed
287 288 289 290 291 292 293 294 295 296 297
		p = r->prog;
		switch(p->as) {
		case AMOVB:
		case AMOVW:
		case AMOVL:
		case AMOVQ:
		case AMOVLQZX:
			if(regtyp(&p->to) && !regconsttyp(&p->from))
				pushback(r);
		}
	}
Russ Cox's avatar
Russ Cox committed
298
	
299
	flowend(g);
Russ Cox's avatar
Russ Cox committed
300 301 302
}

static void
303
pushback(Flow *r0)
Russ Cox's avatar
Russ Cox committed
304
{
305
	Flow *r, *b;
Russ Cox's avatar
Russ Cox committed
306 307
	Prog *p0, *p, t;
	
308
	b = nil;
Russ Cox's avatar
Russ Cox committed
309
	p0 = r0->prog;
310
	for(r=uniqp(r0); r!=nil && uniqs(r)!=nil; r=uniqp(r)) {
Russ Cox's avatar
Russ Cox committed
311 312 313 314
		p = r->prog;
		if(p->as != ANOP) {
			if(!regconsttyp(&p->from) || !regtyp(&p->to))
				break;
315
			if(copyu(p, &p0->to, nil) || copyu(p0, &p->to, nil))
Russ Cox's avatar
Russ Cox committed
316 317 318 319 320 321 322
				break;
		}
		if(p->as == ACALL)
			break;
		b = r;
	}
	
323
	if(b == nil) {
Russ Cox's avatar
Russ Cox committed
324 325 326
		if(debug['v']) {
			print("no pushback: %P\n", r0->prog);
			if(r)
327
				print("\t%P [%d]\n", r->prog, uniqs(r)!=nil);
Russ Cox's avatar
Russ Cox committed
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
		}
		return;
	}

	if(debug['v']) {
		print("pushback\n");
		for(r=b;; r=r->link) {
			print("\t%P\n", r->prog);
			if(r == r0)
				break;
		}
	}

	t = *r0->prog;
	for(r=uniqp(r0);; r=uniqp(r)) {
		p0 = r->link->prog;
		p = r->prog;
		p0->as = p->as;
		p0->lineno = p->lineno;
		p0->from = p->from;
		p0->to = p->to;

		if(r == b)
			break;
	}
	p0 = r->prog;
	p0->as = t.as;
	p0->lineno = t.lineno;
	p0->from = t.from;
	p0->to = t.to;

	if(debug['v']) {
		print("\tafter\n");
		for(r=b;; r=r->link) {
			print("\t%P\n", r->prog);
			if(r == r0)
				break;
		}
	}
Ken Thompson's avatar
Ken Thompson committed
367 368 369
}

void
370
excise(Flow *r)
Ken Thompson's avatar
Ken Thompson committed
371 372 373 374
{
	Prog *p;

	p = r->prog;
Ken Thompson's avatar
Ken Thompson committed
375 376 377
	if(debug['P'] && debug['v'])
		print("%P ===delete===\n", p);

378
	nopout(p);
Ken Thompson's avatar
Ken Thompson committed
379 380

	ostats.ndelmov++;
Ken Thompson's avatar
Ken Thompson committed
381 382
}

Russ Cox's avatar
Russ Cox committed
383
int
Ken Thompson's avatar
Ken Thompson committed
384 385
regtyp(Adr *a)
{
386
	return a->type == TYPE_REG && (REG_AX <= a->reg && a->reg <= REG_R15 || REG_X0 <= a->reg && a->reg <= REG_X15);
Ken Thompson's avatar
Ken Thompson committed
387 388
}

389 390 391 392 393 394 395
// movb elimination.
// movb is simulated by the linker
// when a register other than ax, bx, cx, dx
// is used, so rewrite to other instructions
// when possible.  a movb into a register
// can smash the entire 32-bit register without
// causing any trouble.
396 397 398
//
// TODO: Using the Q forms here instead of the L forms
// seems unnecessary, and it makes the instructions longer.
399
static void
400
elimshortmov(Graph *g)
401 402
{
	Prog *p;
403
	Flow *r;
404

405
	for(r=g->start; r!=nil; r=r->link) {
406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425
		p = r->prog;
		if(regtyp(&p->to)) {
			switch(p->as) {
			case AINCB:
			case AINCW:
				p->as = AINCQ;
				break;
			case ADECB:
			case ADECW:
				p->as = ADECQ;
				break;
			case ANEGB:
			case ANEGW:
				p->as = ANEGQ;
				break;
			case ANOTB:
			case ANOTW:
				p->as = ANOTQ;
				break;
			}
426
			if(regtyp(&p->from) || p->from.type == TYPE_CONST) {
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470
				// move or artihmetic into partial register.
				// from another register or constant can be movl.
				// we don't switch to 64-bit arithmetic if it can
				// change how the carry bit is set (and the carry bit is needed).
				switch(p->as) {
				case AMOVB:
				case AMOVW:
					p->as = AMOVQ;
					break;
				case AADDB:
				case AADDW:
					if(!needc(p->link))
						p->as = AADDQ;
					break;
				case ASUBB:
				case ASUBW:
					if(!needc(p->link))
						p->as = ASUBQ;
					break;
				case AMULB:
				case AMULW:
					p->as = AMULQ;
					break;
				case AIMULB:
				case AIMULW:
					p->as = AIMULQ;
					break;
				case AANDB:
				case AANDW:
					p->as = AANDQ;
					break;
				case AORB:
				case AORW:
					p->as = AORQ;
					break;
				case AXORB:
				case AXORW:
					p->as = AXORQ;
					break;
				case ASHLB:
				case ASHLW:
					p->as = ASHLQ;
					break;
				}
471
			} else if(p->from.type != TYPE_REG) {
472 473 474
				// explicit zero extension, but don't
				// do that if source is a byte register
				// (only AH can occur and it's forbidden).
475 476 477 478 479 480 481 482 483 484 485 486 487
				switch(p->as) {
				case AMOVB:
					p->as = AMOVBQZX;
					break;
				case AMOVW:
					p->as = AMOVWQZX;
					break;
				}
			}
		}
	}
}

488
// is 'a' a register or constant?
489
static int
Russ Cox's avatar
Russ Cox committed
490 491 492 493 494
regconsttyp(Adr *a)
{
	if(regtyp(a))
		return 1;
	switch(a->type) {
495 496 497 498
	case TYPE_CONST:
	case TYPE_FCONST:
	case TYPE_SCONST:
	case TYPE_ADDR: // TODO(rsc): Not all TYPE_ADDRs are constants.
Russ Cox's avatar
Russ Cox committed
499 500 501 502 503 504 505
		return 1;
	}
	return 0;
}

// is reg guaranteed to be truncated by a previous L instruction?
static int
506
prevl(Flow *r0, int reg)
Russ Cox's avatar
Russ Cox committed
507 508
{
	Prog *p;
509
	Flow *r;
510
	ProgInfo info;
Russ Cox's avatar
Russ Cox committed
511

512
	for(r=uniqp(r0); r!=nil; r=uniqp(r)) {
Russ Cox's avatar
Russ Cox committed
513
		p = r->prog;
514
		if(p->to.type == TYPE_REG && p->to.reg == reg) {
515 516 517 518 519
			proginfo(&info, p);
			if(info.flags & RightWrite) {
				if(info.flags & SizeL)
					return 1;
				return 0;
Russ Cox's avatar
Russ Cox committed
520 521 522 523 524 525
			}
		}
	}
	return 0;
}

Ken Thompson's avatar
Ken Thompson committed
526 527 528 529 530 531 532 533 534 535 536 537 538 539
/*
 * 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.
 */
540 541
static int
subprop(Flow *r0)
Ken Thompson's avatar
Ken Thompson committed
542 543
{
	Prog *p;
544
	ProgInfo info;
Ken Thompson's avatar
Ken Thompson committed
545
	Adr *v1, *v2;
546
	Flow *r;
Ken Thompson's avatar
Ken Thompson committed
547 548
	int t;

549 550
	if(debug['P'] && debug['v'])
		print("subprop %P\n", r0->prog);
Ken Thompson's avatar
Ken Thompson committed
551 552
	p = r0->prog;
	v1 = &p->from;
553 554 555
	if(!regtyp(v1)) {
		if(debug['P'] && debug['v'])
			print("\tnot regtype %D; return 0\n", v1);
Ken Thompson's avatar
Ken Thompson committed
556
		return 0;
557
	}
Ken Thompson's avatar
Ken Thompson committed
558
	v2 = &p->to;
559 560 561
	if(!regtyp(v2)) {
		if(debug['P'] && debug['v'])
			print("\tnot regtype %D; return 0\n", v2);
Ken Thompson's avatar
Ken Thompson committed
562
		return 0;
563
	}
564
	for(r=uniqp(r0); r!=nil; r=uniqp(r)) {
565 566
		if(debug['P'] && debug['v'])
			print("\t? %P\n", r->prog);
567
		if(uniqs(r) == nil) {
568 569
			if(debug['P'] && debug['v'])
				print("\tno unique successor\n");
Ken Thompson's avatar
Ken Thompson committed
570
			break;
571
		}
Ken Thompson's avatar
Ken Thompson committed
572
		p = r->prog;
573
		if(p->as == AVARDEF || p->as == AVARKILL)
574
			continue;
575 576
		proginfo(&info, p);
		if(info.flags & Call) {
577 578
			if(debug['P'] && debug['v'])
				print("\tfound %P; return 0\n", p);
Ken Thompson's avatar
Ken Thompson committed
579
			return 0;
580
		}
Ken Thompson's avatar
Ken Thompson committed
581

582
		if(info.reguse | info.regset) {
583 584
			if(debug['P'] && debug['v'])
				print("\tfound %P; return 0\n", p);
Ken Thompson's avatar
Ken Thompson committed
585 586
			return 0;
		}
587

588
		if((info.flags & Move) && (info.flags & (SizeL|SizeQ|SizeF|SizeD)) && p->to.type == v1->type && p->to.reg == v1->reg)
589 590
			goto gotit;

Ken Thompson's avatar
Ken Thompson committed
591
		if(copyau(&p->from, v2) ||
592 593 594
		   copyau(&p->to, v2)) {
		   	if(debug['P'] && debug['v'])
		   		print("\tcopyau %D failed\n", v2);
Ken Thompson's avatar
Ken Thompson committed
595
			break;
596
		}
Ken Thompson's avatar
Ken Thompson committed
597
		if(copysub(&p->from, v1, v2, 0) ||
598 599 600
		   copysub(&p->to, v1, v2, 0)) {
		   	if(debug['P'] && debug['v'])
		   		print("\tcopysub failed\n");
Ken Thompson's avatar
Ken Thompson committed
601
			break;
602
		}
Ken Thompson's avatar
Ken Thompson committed
603
	}
604
	if(debug['P'] && debug['v'])
605
		print("\tran off end; return 0\n");
Ken Thompson's avatar
Ken Thompson committed
606 607 608 609 610 611
	return 0;

gotit:
	copysub(&p->to, v1, v2, 1);
	if(debug['P']) {
		print("gotit: %D->%D\n%P", v1, v2, r->prog);
612
		if(p->from.type == v2->type && p->from.reg == v2->reg)
Ken Thompson's avatar
Ken Thompson committed
613 614 615 616 617 618 619 620 621 622
			print(" excise");
		print("\n");
	}
	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
		p = r->prog;
		copysub(&p->from, v1, v2, 1);
		copysub(&p->to, v1, v2, 1);
		if(debug['P'])
			print("%P\n", r->prog);
	}
623 624 625
	t = v1->reg;
	v1->reg = v2->reg;
	v2->reg = t;
Ken Thompson's avatar
Ken Thompson committed
626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642
	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
 */
643 644
static int
copyprop(Graph *g, Flow *r0)
Ken Thompson's avatar
Ken Thompson committed
645 646 647 648
{
	Prog *p;
	Adr *v1, *v2;

649
	USED(g);
650 651
	if(debug['P'] && debug['v'])
		print("copyprop %P\n", r0->prog);
Ken Thompson's avatar
Ken Thompson committed
652 653 654 655 656
	p = r0->prog;
	v1 = &p->from;
	v2 = &p->to;
	if(copyas(v1, v2))
		return 1;
657
	gactive++;
Ken Thompson's avatar
Ken Thompson committed
658 659 660
	return copy1(v1, v2, r0->s1, 0);
}

661 662
static int
copy1(Adr *v1, Adr *v2, Flow *r, int f)
Ken Thompson's avatar
Ken Thompson committed
663 664 665 666
{
	int t;
	Prog *p;

667
	if(r->active == gactive) {
Ken Thompson's avatar
Ken Thompson committed
668 669 670 671
		if(debug['P'])
			print("act set; return 1\n");
		return 1;
	}
672
	r->active = gactive;
Ken Thompson's avatar
Ken Thompson committed
673 674
	if(debug['P'])
		print("copy %D->%D f=%d\n", v1, v2, f);
675
	for(; r != nil; r = r->s1) {
Ken Thompson's avatar
Ken Thompson committed
676 677 678
		p = r->prog;
		if(debug['P'])
			print("%P", p);
679
		if(!f && uniqp(r) == nil) {
Ken Thompson's avatar
Ken Thompson committed
680 681 682 683
			f = 1;
			if(debug['P'])
				print("; merge; f=%d", f);
		}
684
		t = copyu(p, v2, nil);
Ken Thompson's avatar
Ken Thompson committed
685
		switch(t) {
Shenghou Ma's avatar
Shenghou Ma committed
686
		case 2:	/* rar, can't split */
Ken Thompson's avatar
Ken Thompson committed
687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721
			if(debug['P'])
				print("; %D rar; return 0\n", v2);
			return 0;

		case 3:	/* set */
			if(debug['P'])
				print("; %D set; 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("; %D used+set and f=%d; return 0\n", v2, f);
				else
					print("; %D used 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("; %D used+set; return 1\n", v2);
				return 1;
			}
			break;
		}
		if(!f) {
722
			t = copyu(p, v1, nil);
Ken Thompson's avatar
Ken Thompson committed
723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745
			if(!f && (t == 2 || t == 3 || t == 4)) {
				f = 1;
				if(debug['P'])
					print("; %D set 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;
}

/*
 * 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)
 */
746
static int
Ken Thompson's avatar
Ken Thompson committed
747 748
copyu(Prog *p, Adr *v, Adr *s)
{
749
	ProgInfo info;
Ken Thompson's avatar
Ken Thompson committed
750 751

	switch(p->as) {
752
	case AJMP:
753
		if(s != nil) {
Ken Thompson's avatar
Ken Thompson committed
754 755 756 757 758 759 760 761
			if(copysub(&p->to, v, s, 1))
				return 1;
			return 0;
		}
		if(copyau(&p->to, v))
			return 1;
		return 0;

762
	case ARET:
763
		if(s != nil)
Ken Thompson's avatar
Ken Thompson committed
764 765 766
			return 1;
		return 3;

767
	case ACALL:
768
		if(REGEXT && v->type == TYPE_REG && v->reg <= REGEXT && v->reg > exregoffset)
Ken Thompson's avatar
Ken Thompson committed
769
			return 2;
770
		if(REGARG >= 0 && v->type == TYPE_REG && v->reg == REGARG)
Ken Thompson's avatar
Ken Thompson committed
771
			return 2;
772
		if(v->type == p->from.type && v->reg == p->from.reg)
773
			return 2;
Ken Thompson's avatar
Ken Thompson committed
774

775
		if(s != nil) {
Ken Thompson's avatar
Ken Thompson committed
776 777 778 779 780 781 782 783
			if(copysub(&p->to, v, s, 1))
				return 1;
			return 0;
		}
		if(copyau(&p->to, v))
			return 4;
		return 3;

784
	case ATEXT:
785
		if(REGARG >= 0 && v->type == TYPE_REG && v->reg == REGARG)
Ken Thompson's avatar
Ken Thompson committed
786 787 788
			return 3;
		return 0;
	}
789

790
	if(p->as == AVARDEF || p->as == AVARKILL)
791
		return 0;
792 793
	proginfo(&info, p);

794
	if((info.reguse|info.regset) & RtoB(v->reg))
795 796 797 798 799 800 801 802 803 804 805 806
		return 2;
		
	if(info.flags & LeftAddr)
		if(copyas(&p->from, v))
			return 2;

	if((info.flags & (RightRead|RightWrite)) == (RightRead|RightWrite))
		if(copyas(&p->to, v))
			return 2;
	
	if(info.flags & RightWrite) {
		if(copyas(&p->to, v)) {
807
			if(s != nil)
808 809 810 811 812 813 814 815
				return copysub(&p->from, v, s, 1);
			if(copyau(&p->from, v))
				return 4;
			return 3;
		}
	}
	
	if(info.flags & (LeftAddr|LeftRead|LeftWrite|RightAddr|RightRead|RightWrite)) {
816
		if(s != nil) {
817 818 819 820 821 822 823 824 825 826
			if(copysub(&p->from, v, s, 1))
				return 1;
			return copysub(&p->to, v, s, 1);
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau(&p->to, v))
			return 1;
	}

Ken Thompson's avatar
Ken Thompson committed
827 828 829 830 831 832 833 834
	return 0;
}

/*
 * direct reference,
 * could be set/use depending on
 * semantics
 */
835
static int
Ken Thompson's avatar
Ken Thompson committed
836 837
copyas(Adr *a, Adr *v)
{
838
	if(REG_AL <= a->reg && a->reg <= REG_R15B)
839
		fatal("use of byte register");
840
	if(REG_AL <= v->reg && v->reg <= REG_R15B)
841 842
		fatal("use of byte register");

843
	if(a->type != v->type || a->name != v->name || a->reg != v->reg)
Ken Thompson's avatar
Ken Thompson committed
844 845 846
		return 0;
	if(regtyp(v))
		return 1;
847
	if(v->type == TYPE_MEM && (v->name == NAME_AUTO || v->name == NAME_PARAM))
Ken Thompson's avatar
Ken Thompson committed
848 849 850 851 852
		if(v->offset == a->offset)
			return 1;
	return 0;
}

853 854 855
int
sameaddr(Addr *a, Addr *v)
{
856
	if(a->type != v->type || a->name != v->name || a->reg != v->reg)
857 858 859
		return 0;
	if(regtyp(v))
		return 1;
860
	if(v->type == TYPE_MEM && (v->name == NAME_AUTO || v->name == NAME_PARAM))
861 862 863 864 865
		if(v->offset == a->offset)
			return 1;
	return 0;
}

Ken Thompson's avatar
Ken Thompson committed
866 867 868
/*
 * either direct or indirect
 */
869
static int
Ken Thompson's avatar
Ken Thompson committed
870 871 872
copyau(Adr *a, Adr *v)
{

873 874 875
	if(copyas(a, v)) {
		if(debug['P'] && debug['v'])
			print("\tcopyau: copyas returned 1\n");
Ken Thompson's avatar
Ken Thompson committed
876
		return 1;
877
	}
Ken Thompson's avatar
Ken Thompson committed
878
	if(regtyp(v)) {
879
		if(a->type == TYPE_MEM && a->reg == v->reg) {
880 881
			if(debug['P'] && debug['v'])
				print("\tcopyau: found indir use - return 1\n");
Ken Thompson's avatar
Ken Thompson committed
882
			return 1;
883
		}
884
		if(a->index == v->reg) {
885 886
			if(debug['P'] && debug['v'])
				print("\tcopyau: found index use - return 1\n");
Ken Thompson's avatar
Ken Thompson committed
887
			return 1;
888
		}
Ken Thompson's avatar
Ken Thompson committed
889 890 891 892 893 894 895 896
	}
	return 0;
}

/*
 * substitute s for v in a
 * return failure to substitute
 */
897
static int
Ken Thompson's avatar
Ken Thompson committed
898 899
copysub(Adr *a, Adr *v, Adr *s, int f)
{
900
	int reg;
Ken Thompson's avatar
Ken Thompson committed
901 902

	if(copyas(a, v)) {
903 904
		reg = s->reg;
		if(reg >= REG_AX && reg <= REG_R15 || reg >= REG_X0 && reg <= REG_X0+15) {
Ken Thompson's avatar
Ken Thompson committed
905
			if(f)
906
				a->reg = reg;
Ken Thompson's avatar
Ken Thompson committed
907 908 909 910
		}
		return 0;
	}
	if(regtyp(v)) {
911 912 913
		reg = v->reg;
		if(a->type == TYPE_MEM && a->reg == reg) {
			if((s->reg == REG_BP || s->reg == REG_R13) && a->index != REG_NONE)
Ken Thompson's avatar
Ken Thompson committed
914 915
				return 1;	/* can't use BP-base with index */
			if(f)
916
				a->reg = s->reg;
Ken Thompson's avatar
Ken Thompson committed
917 918
//			return 0;
		}
919
		if(a->index == reg) {
Ken Thompson's avatar
Ken Thompson committed
920
			if(f)
921
				a->index = s->reg;
Ken Thompson's avatar
Ken Thompson committed
922 923 924 925 926 927
			return 0;
		}
		return 0;
	}
	return 0;
}
Ken Thompson's avatar
Ken Thompson committed
928 929

static void
930
conprop(Flow *r0)
Ken Thompson's avatar
Ken Thompson committed
931
{
932
	Flow *r;
Ken Thompson's avatar
Ken Thompson committed
933 934 935 936 937 938 939 940 941 942
	Prog *p, *p0;
	int t;
	Adr *v0;

	p0 = r0->prog;
	v0 = &p0->to;
	r = r0;

loop:
	r = uniqs(r);
943
	if(r == nil || r == r0)
Ken Thompson's avatar
Ken Thompson committed
944
		return;
945
	if(uniqp(r) == nil)
Ken Thompson's avatar
Ken Thompson committed
946 947 948
		return;

	p = r->prog;
949
	t = copyu(p, v0, nil);
Ken Thompson's avatar
Ken Thompson committed
950 951 952 953 954 955 956 957 958 959 960 961
	switch(t) {
	case 0:	// miss
	case 1:	// use
		goto loop;

	case 2:	// rar
	case 4:	// use and set
		break;

	case 3:	// set
		if(p->as == p0->as)
		if(p->from.type == p0->from.type)
962
		if(p->from.reg == p0->from.reg)
963
		if(p->from.node == p0->from.node)
Ken Thompson's avatar
Ken Thompson committed
964 965
		if(p->from.offset == p0->from.offset)
		if(p->from.scale == p0->from.scale)
966
		if(p->from.type == TYPE_FCONST && p->from.u.dval == p0->from.u.dval)
Ken Thompson's avatar
Ken Thompson committed
967 968 969 970 971 972 973
		if(p->from.index == p0->from.index) {
			excise(r);
			goto loop;
		}
		break;
	}
}
974 975 976 977 978

int
smallindir(Addr *a, Addr *reg)
{
	return regtyp(reg) &&
979 980
		a->type == TYPE_MEM && a->reg == reg->reg &&
		a->index == REG_NONE &&
981 982 983 984 985 986
		0 <= a->offset && a->offset < 4096;
}

int
stackaddr(Addr *a)
{
987
	return a->type == TYPE_REG && a->reg == REG_SP;
988
}