reg.go 28.3 KB
Newer Older
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
// 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.

package gc

import (
	"cmd/internal/obj"
	"fmt"
	"sort"
)

var firstf *Flow

var first int = 1

type rcmp []Rgn

func (x rcmp) Len() int {
	return len(x)
}

func (x rcmp) Swap(i, j int) {
	x[i], x[j] = x[j], x[i]
}

func (x rcmp) Less(i, j int) bool {
54 55
	p1 := &x[i]
	p2 := &x[j]
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
	if p1.cost != p2.cost {
		return int(p2.cost)-int(p1.cost) < 0
	}
	if p1.varno != p2.varno {
		return int(p2.varno)-int(p1.varno) < 0
	}
	if p1.enter != p2.enter {
		return int(p2.enter.Id-p1.enter.Id) < 0
	}
	return false
}

func setaddrs(bit Bits) {
	var i int
	var n int
	var v *Var
	var node *Node

74
	for bany(&bit) {
75 76 77 78 79 80 81 82 83
		// convert each bit to a variable
		i = bnum(bit)

		node = var_[i].node
		n = int(var_[i].name)
		biclr(&bit, uint(i))

		// disable all pieces of that variable
		for i = 0; i < nvar; i++ {
84
			v = &var_[i]
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
			if v.node == node && int(v.name) == n {
				v.addr = 2
			}
		}
	}
}

var regnodes [64]*Node

func walkvardef(n *Node, f *Flow, active int) {
	var f1 *Flow
	var bn int
	var v *Var

	for f1 = f; f1 != nil; f1 = f1.S1 {
		if f1.Active == int32(active) {
			break
		}
		f1.Active = int32(active)
		if f1.Prog.As == obj.AVARKILL && f1.Prog.To.Node == n {
			break
		}
		for v, _ = n.Opt.(*Var); v != nil; v = v.nextinnode {
			bn = v.id
			biset(&(f1.Data.(*Reg)).act, uint(bn))
		}

		if f1.Prog.As == obj.ACALL {
			break
		}
	}

117
	for f2 := f; f2 != f1; f2 = f2.S1 {
118 119 120 121 122 123 124 125 126 127 128
		if f2.S2 != nil {
			walkvardef(n, f2.S2, active)
		}
	}
}

/*
 * add mov b,rn
 * just after r
 */
func addmove(r *Flow, bn int, rn int, f int) {
129
	p1 := Ctxt.NewProg()
130 131 132
	Clearp(p1)
	p1.Pc = 9999

133
	p := r.Prog
134 135 136 137
	p1.Link = p.Link
	p.Link = p1
	p1.Lineno = p.Lineno

138
	v := &var_[bn]
139

140
	a := &p1.To
141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
	a.Offset = v.offset
	a.Etype = uint8(v.etype)
	a.Type = obj.TYPE_MEM
	a.Name = v.name
	a.Node = v.node
	a.Sym = Linksym(v.node.Sym)

	/* NOTE(rsc): 9g did
	if(a->etype == TARRAY)
		a->type = TYPE_ADDR;
	else if(a->sym == nil)
		a->type = TYPE_CONST;
	*/
	p1.As = int16(Thearch.Optoas(OAS, Types[uint8(v.etype)]))

	// TODO(rsc): Remove special case here.
	if (Thearch.Thechar == '9' || Thearch.Thechar == '5') && v.etype == TBOOL {
		p1.As = int16(Thearch.Optoas(OAS, Types[TUINT8]))
	}
	p1.From.Type = obj.TYPE_REG
	p1.From.Reg = int16(rn)
	p1.From.Name = obj.NAME_NONE
163
	if f == 0 {
164
		p1.From = *a
165
		*a = obj.Addr{}
166 167 168 169 170 171 172 173 174 175
		a.Type = obj.TYPE_REG
		a.Reg = int16(rn)
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		fmt.Printf("%v ===add=== %v\n", p, p1)
	}
	Ostats.Nspill++
}

176
func overlap_reg(o1 int64, w1 int, o2 int64, w2 int) bool {
177 178
	t1 := o1 + int64(w1)
	t2 := o2 + int64(w2)
179

180 181
	if t1 <= o2 || t2 <= o1 {
		return false
182 183
	}

184
	return true
185 186 187 188 189 190 191
}

func mkvar(f *Flow, a *obj.Addr) Bits {
	/*
	 * mark registers used
	 */
	if a.Type == obj.TYPE_NONE {
Russ Cox's avatar
Russ Cox committed
192
		return zbits
193 194
	}

Russ Cox's avatar
Russ Cox committed
195
	r := f.Data.(*Reg)
196 197
	r.use1.b[0] |= Thearch.Doregbits(int(a.Index)) // TODO: Use RtoB

Russ Cox's avatar
Russ Cox committed
198
	var n int
199 200
	switch a.Type {
	default:
201
		regu := Thearch.Doregbits(int(a.Reg)) | Thearch.RtoB(int(a.Reg)) // TODO: Use RtoB
202
		if regu == 0 {
Russ Cox's avatar
Russ Cox committed
203
			return zbits
204
		}
205
		bit := zbits
206 207 208 209 210
		bit.b[0] = regu
		return bit

		// TODO(rsc): Remove special case here.
	case obj.TYPE_ADDR:
211
		var bit Bits
212 213 214 215 216 217 218 219
		if Thearch.Thechar == '9' || Thearch.Thechar == '5' {
			goto memcase
		}
		a.Type = obj.TYPE_MEM
		bit = mkvar(f, a)
		setaddrs(bit)
		a.Type = obj.TYPE_ADDR
		Ostats.Naddr++
Russ Cox's avatar
Russ Cox committed
220
		return zbits
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235

	memcase:
		fallthrough

	case obj.TYPE_MEM:
		if r != R {
			r.use1.b[0] |= Thearch.RtoB(int(a.Reg))
		}

		/* NOTE: 5g did
		if(r->f.prog->scond & (C_PBIT|C_WBIT))
			r->set.b[0] |= RtoB(a->reg);
		*/
		switch a.Name {
		default:
Russ Cox's avatar
Russ Cox committed
236
			return zbits
237 238 239 240 241 242 243 244 245

		case obj.NAME_EXTERN,
			obj.NAME_STATIC,
			obj.NAME_PARAM,
			obj.NAME_AUTO:
			n = int(a.Name)
		}
	}

Russ Cox's avatar
Russ Cox committed
246
	var node *Node
247 248
	node, _ = a.Node.(*Node)
	if node == nil || node.Op != ONAME || node.Orig == nil {
Russ Cox's avatar
Russ Cox committed
249
		return zbits
250 251 252 253 254 255
	}
	node = node.Orig
	if node.Orig != node {
		Fatal("%v: bad node", Ctxt.Dconv(a))
	}
	if node.Sym == nil || node.Sym.Name[0] == '.' {
Russ Cox's avatar
Russ Cox committed
256
		return zbits
257
	}
Russ Cox's avatar
Russ Cox committed
258 259 260
	et := int(a.Etype)
	o := a.Offset
	w := a.Width
261 262 263 264
	if w < 0 {
		Fatal("bad width %d for %v", w, Ctxt.Dconv(a))
	}

Russ Cox's avatar
Russ Cox committed
265 266
	flag := 0
	var v *Var
267
	for i := 0; i < nvar; i++ {
268
		v = &var_[i]
269 270 271 272 273
		if v.node == node && int(v.name) == n {
			if v.offset == o {
				if int(v.etype) == et {
					if int64(v.width) == w {
						// TODO(rsc): Remove special case for arm here.
274
						if flag == 0 || Thearch.Thechar != '5' {
275 276 277 278 279 280 281
							return blsh(uint(i))
						}
					}
				}
			}

			// if they overlap, disable both
282
			if overlap_reg(v.offset, v.width, o, int(w)) {
283 284 285 286 287 288 289 290 291 292 293
				//				print("disable overlap %s %d %d %d %d, %E != %E\n", s->name, v->offset, v->width, o, w, v->etype, et);
				v.addr = 1

				flag = 1
			}
		}
	}

	switch et {
	case 0,
		TFUNC:
Russ Cox's avatar
Russ Cox committed
294
		return zbits
295 296 297 298 299 300 301 302 303 304 305
	}

	if nvar >= NVAR {
		if Debug['w'] > 1 && node != nil {
			Fatal("variable not optimized: %v", Nconv(node, obj.FmtSharp))
		}

		// If we're not tracking a word in a variable, mark the rest as
		// having its address taken, so that we keep the whole thing
		// live at all calls. otherwise we might optimize away part of
		// a variable but not all of it.
306 307
		var v *Var
		for i := 0; i < nvar; i++ {
308
			v = &var_[i]
309 310 311 312 313
			if v.node == node {
				v.addr = 1
			}
		}

Russ Cox's avatar
Russ Cox committed
314
		return zbits
315 316
	}

Russ Cox's avatar
Russ Cox committed
317
	i := nvar
318
	nvar++
319
	v = &var_[i]
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335
	v.id = i
	v.offset = o
	v.name = int8(n)
	v.etype = int8(et)
	v.width = int(w)
	v.addr = int8(flag) // funny punning
	v.node = node

	// node->opt is the head of a linked list
	// of Vars within the given Node, so that
	// we can start at a Var and find all the other
	// Vars in the same Go variable.
	v.nextinnode, _ = node.Opt.(*Var)

	node.Opt = v

Russ Cox's avatar
Russ Cox committed
336
	bit := blsh(uint(i))
337
	if n == obj.NAME_EXTERN || n == obj.NAME_STATIC {
338
		for z := 0; z < BITS; z++ {
339 340 341 342
			externs.b[z] |= bit.b[z]
		}
	}
	if n == obj.NAME_PARAM {
343
		for z := 0; z < BITS; z++ {
344 345 346 347 348
			params.b[z] |= bit.b[z]
		}
	}

	if node.Class == PPARAM {
349
		for z := 0; z < BITS; z++ {
350 351 352 353
			ivar.b[z] |= bit.b[z]
		}
	}
	if node.Class == PPARAMOUT {
354
		for z := 0; z < BITS; z++ {
355 356 357 358 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 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
			ovar.b[z] |= bit.b[z]
		}
	}

	// Treat values with their address taken as live at calls,
	// because the garbage collector's liveness analysis in ../gc/plive.c does.
	// These must be consistent or else we will elide stores and the garbage
	// collector will see uninitialized data.
	// The typical case where our own analysis is out of sync is when the
	// node appears to have its address taken but that code doesn't actually
	// get generated and therefore doesn't show up as an address being
	// taken when we analyze the instruction stream.
	// One instance of this case is when a closure uses the same name as
	// an outer variable for one of its own variables declared with :=.
	// The parser flags the outer variable as possibly shared, and therefore
	// sets addrtaken, even though it ends up not being actually shared.
	// If we were better about _ elision, _ = &x would suffice too.
	// The broader := in a closure problem is mentioned in a comment in
	// closure.c:/^typecheckclosure and dcl.c:/^oldname.
	if node.Addrtaken != 0 {
		v.addr = 1
	}

	// Disable registerization for globals, because:
	// (1) we might panic at any time and we want the recovery code
	// to see the latest values (issue 1304).
	// (2) we don't know what pointers might point at them and we want
	// loads via those pointers to see updated values and vice versa (issue 7995).
	//
	// Disable registerization for results if using defer, because the deferred func
	// might recover and return, causing the current values to be used.
	if node.Class == PEXTERN || (Hasdefer != 0 && node.Class == PPARAMOUT) {
		v.addr = 1
	}

	if Debug['R'] != 0 {
		fmt.Printf("bit=%2d et=%v w=%d+%d %v %v flag=%d\n", i, Econv(int(et), 0), o, w, Nconv(node, obj.FmtSharp), Ctxt.Dconv(a), v.addr)
	}
	Ostats.Nvar++

	return bit
}

func prop(f *Flow, ref Bits, cal Bits) {
	var f1 *Flow
	var r1 *Reg
	var z int
	var i int
	var v *Var
	var v1 *Var

	for f1 = f; f1 != nil; f1 = f1.P1 {
		r1 = f1.Data.(*Reg)
		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 f1.Prog.As {
		case obj.ACALL:
424
			if Noreturn(f1.Prog) {
425 426 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
				break
			}

			// Mark all input variables (ivar) as used, because that's what the
			// liveness bitmaps say. The liveness bitmaps say that so that a
			// panic will not show stale values in the parameter dump.
			// Mark variables with a recent VARDEF (r1->act) as used,
			// so that the optimizer flushes initializations to memory,
			// so that if a garbage collection happens during this CALL,
			// the collector will see initialized memory. Again this is to
			// match what the liveness bitmaps say.
			for z = 0; z < BITS; z++ {
				cal.b[z] |= ref.b[z] | externs.b[z] | ivar.b[z] | r1.act.b[z]
				ref.b[z] = 0
			}

			// cal.b is the current approximation of what's live across the call.
			// Every bit in cal.b is a single stack word. For each such word,
			// find all the other tracked stack words in the same Go variable
			// (struct/slice/string/interface) and mark them live too.
			// This is necessary because the liveness analysis for the garbage
			// collector works at variable granularity, not at word granularity.
			// It is fundamental for slice/string/interface: the garbage collector
			// needs the whole value, not just some of the words, in order to
			// interpret the other bits correctly. Specifically, slice needs a consistent
			// ptr and cap, string needs a consistent ptr and len, and interface
			// needs a consistent type word and data word.
			for z = 0; z < BITS; z++ {
				if cal.b[z] == 0 {
					continue
				}
				for i = 0; i < 64; i++ {
					if z*64+i >= nvar || (cal.b[z]>>uint(i))&1 == 0 {
						continue
					}
460
					v = &var_[z*64+i]
461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476
					if v.node.Opt == nil { // v represents fixed register, not Go variable
						continue
					}

					// v->node->opt is the head of a linked list of Vars
					// corresponding to tracked words from the Go variable v->node.
					// Walk the list and set all the bits.
					// For a large struct this could end up being quadratic:
					// after the first setting, the outer loop (for z, i) would see a 1 bit
					// for all of the remaining words in the struct, and for each such
					// word would go through and turn on all the bits again.
					// To avoid the quadratic behavior, we only turn on the bits if
					// v is the head of the list or if the head's bit is not yet turned on.
					// This will set the bits at most twice, keeping the overall loop linear.
					v1, _ = v.node.Opt.(*Var)

477
					if v == v1 || !btest(&cal, uint(v1.id)) {
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
						for ; v1 != nil; v1 = v1.nextinnode {
							biset(&cal, uint(v1.id))
						}
					}
				}
			}

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

		case obj.ARET:
			for z = 0; z < BITS; z++ {
				cal.b[z] = externs.b[z] | ovar.b[z]
				ref.b[z] = 0
			}
		}

		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 f1.Active != 0 {
			break
		}
		f1.Active = 1
	}

511 512
	var r *Reg
	var f2 *Flow
513 514 515 516 517 518 519 520 521 522 523 524
	for ; f != f1; f = f.P1 {
		r = f.Data.(*Reg)
		for f2 = f.P2; f2 != nil; f2 = f2.P2link {
			prop(f2, r.refbehind, r.calbehind)
		}
	}
}

func synch(f *Flow, dif Bits) {
	var r1 *Reg
	var z int

525
	for f1 := f; f1 != nil; f1 = f1.S1 {
526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
		r1 = f1.Data.(*Reg)
		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 f1.Active != 0 {
			break
		}
		f1.Active = 1
		for z = 0; z < BITS; z++ {
			dif.b[z] &^= (^r1.calbehind.b[z] & r1.calahead.b[z])
		}
		if f1.S2 != nil {
			synch(f1.S2, dif)
		}
	}
}

func allreg(b uint64, r *Rgn) uint64 {
549
	v := &var_[r.varno]
550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568
	r.regno = 0
	switch v.etype {
	default:
		Fatal("unknown etype %d/%v", Bitno(b), Econv(int(v.etype), 0))

	case TINT8,
		TUINT8,
		TINT16,
		TUINT16,
		TINT32,
		TUINT32,
		TINT64,
		TUINT64,
		TINT,
		TUINT,
		TUINTPTR,
		TBOOL,
		TPTR32,
		TPTR64:
569
		i := Thearch.BtoR(^b)
570 571 572 573 574 575 576
		if i != 0 && r.cost > 0 {
			r.regno = int16(i)
			return Thearch.RtoB(i)
		}

	case TFLOAT32,
		TFLOAT64:
577
		i := Thearch.BtoF(^b)
578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595
		if i != 0 && r.cost > 0 {
			r.regno = int16(i)
			return Thearch.FtoB(i)
		}
	}

	return 0
}

func LOAD(r *Reg, z int) uint64 {
	return ^r.refbehind.b[z] & r.refahead.b[z]
}

func STORE(r *Reg, z int) uint64 {
	return ^r.calbehind.b[z] & r.calahead.b[z]
}

func paint1(f *Flow, bn int) {
596 597 598
	z := bn / 64
	bb := uint64(1 << uint(bn%64))
	r := f.Data.(*Reg)
599 600 601
	if r.act.b[z]&bb != 0 {
		return
	}
602 603
	var f1 *Flow
	var r1 *Reg
604
	for {
605
		if r.refbehind.b[z]&bb == 0 {
606 607 608 609 610 611 612
			break
		}
		f1 = f.P1
		if f1 == nil {
			break
		}
		r1 = f1.Data.(*Reg)
613
		if r1.refahead.b[z]&bb == 0 {
614 615 616 617 618 619 620 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 649 650
			break
		}
		if r1.act.b[z]&bb != 0 {
			break
		}
		f = f1
		r = r1
	}

	if LOAD(r, z)&^(r.set.b[z]&^(r.use1.b[z]|r.use2.b[z]))&bb != 0 {
		change -= CLOAD * int(f.Loop)
	}

	for {
		r.act.b[z] |= bb

		if f.Prog.As != obj.ANOP { // don't give credit for NOPs
			if r.use1.b[z]&bb != 0 {
				change += CREF * int(f.Loop)
			}
			if (r.use2.b[z]|r.set.b[z])&bb != 0 {
				change += CREF * int(f.Loop)
			}
		}

		if STORE(r, z)&r.regdiff.b[z]&bb != 0 {
			change -= CLOAD * int(f.Loop)
		}

		if r.refbehind.b[z]&bb != 0 {
			for f1 = f.P2; f1 != nil; f1 = f1.P2link {
				if (f1.Data.(*Reg)).refahead.b[z]&bb != 0 {
					paint1(f1, bn)
				}
			}
		}

651
		if r.refahead.b[z]&bb == 0 {
652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667
			break
		}
		f1 = f.S2
		if f1 != nil {
			if (f1.Data.(*Reg)).refbehind.b[z]&bb != 0 {
				paint1(f1, bn)
			}
		}
		f = f.S1
		if f == nil {
			break
		}
		r = f.Data.(*Reg)
		if r.act.b[z]&bb != 0 {
			break
		}
668
		if r.refbehind.b[z]&bb == 0 {
669 670 671 672 673 674
			break
		}
	}
}

func paint2(f *Flow, bn int, depth int) uint64 {
675 676 677 678
	z := bn / 64
	bb := uint64(1 << uint(bn%64))
	vreg := regbits
	r := f.Data.(*Reg)
679
	if r.act.b[z]&bb == 0 {
680 681
		return vreg
	}
682 683
	var r1 *Reg
	var f1 *Flow
684
	for {
685
		if r.refbehind.b[z]&bb == 0 {
686 687 688 689 690 691 692
			break
		}
		f1 = f.P1
		if f1 == nil {
			break
		}
		r1 = f1.Data.(*Reg)
693
		if r1.refahead.b[z]&bb == 0 {
694 695
			break
		}
696
		if r1.act.b[z]&bb == 0 {
697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719
			break
		}
		f = f1
		r = r1
	}

	for {
		if Debug['R'] != 0 && Debug['v'] != 0 {
			fmt.Printf("  paint2 %d %v\n", depth, f.Prog)
		}

		r.act.b[z] &^= bb

		vreg |= r.regu

		if r.refbehind.b[z]&bb != 0 {
			for f1 = f.P2; f1 != nil; f1 = f1.P2link {
				if (f1.Data.(*Reg)).refahead.b[z]&bb != 0 {
					vreg |= paint2(f1, bn, depth+1)
				}
			}
		}

720
		if r.refahead.b[z]&bb == 0 {
721 722 723 724 725 726 727 728 729 730 731 732 733
			break
		}
		f1 = f.S2
		if f1 != nil {
			if (f1.Data.(*Reg)).refbehind.b[z]&bb != 0 {
				vreg |= paint2(f1, bn, depth+1)
			}
		}
		f = f.S1
		if f == nil {
			break
		}
		r = f.Data.(*Reg)
734
		if r.act.b[z]&bb == 0 {
735 736
			break
		}
737
		if r.refbehind.b[z]&bb == 0 {
738 739 740 741 742 743 744 745
			break
		}
	}

	return vreg
}

func paint3(f *Flow, bn int, rb uint64, rn int) {
746 747 748
	z := bn / 64
	bb := uint64(1 << uint(bn%64))
	r := f.Data.(*Reg)
749 750 751
	if r.act.b[z]&bb != 0 {
		return
	}
752 753
	var r1 *Reg
	var f1 *Flow
754
	for {
755
		if r.refbehind.b[z]&bb == 0 {
756 757 758 759 760 761 762
			break
		}
		f1 = f.P1
		if f1 == nil {
			break
		}
		r1 = f1.Data.(*Reg)
763
		if r1.refahead.b[z]&bb == 0 {
764 765 766 767 768 769 770 771 772 773 774 775
			break
		}
		if r1.act.b[z]&bb != 0 {
			break
		}
		f = f1
		r = r1
	}

	if LOAD(r, z)&^(r.set.b[z]&^(r.use1.b[z]|r.use2.b[z]))&bb != 0 {
		addmove(f, bn, rn, 0)
	}
776
	var p *obj.Prog
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813
	for {
		r.act.b[z] |= bb
		p = f.Prog

		if r.use1.b[z]&bb != 0 {
			if Debug['R'] != 0 && Debug['v'] != 0 {
				fmt.Printf("%v", p)
			}
			addreg(&p.From, rn)
			if Debug['R'] != 0 && Debug['v'] != 0 {
				fmt.Printf(" ===change== %v\n", p)
			}
		}

		if (r.use2.b[z]|r.set.b[z])&bb != 0 {
			if Debug['R'] != 0 && Debug['v'] != 0 {
				fmt.Printf("%v", p)
			}
			addreg(&p.To, rn)
			if Debug['R'] != 0 && Debug['v'] != 0 {
				fmt.Printf(" ===change== %v\n", p)
			}
		}

		if STORE(r, z)&r.regdiff.b[z]&bb != 0 {
			addmove(f, bn, rn, 1)
		}
		r.regu |= rb

		if r.refbehind.b[z]&bb != 0 {
			for f1 = f.P2; f1 != nil; f1 = f1.P2link {
				if (f1.Data.(*Reg)).refahead.b[z]&bb != 0 {
					paint3(f1, bn, rb, rn)
				}
			}
		}

814
		if r.refahead.b[z]&bb == 0 {
815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830
			break
		}
		f1 = f.S2
		if f1 != nil {
			if (f1.Data.(*Reg)).refbehind.b[z]&bb != 0 {
				paint3(f1, bn, rb, rn)
			}
		}
		f = f.S1
		if f == nil {
			break
		}
		r = f.Data.(*Reg)
		if r.act.b[z]&bb != 0 {
			break
		}
831
		if r.refbehind.b[z]&bb == 0 {
832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
			break
		}
	}
}

func addreg(a *obj.Addr, rn int) {
	a.Sym = nil
	a.Node = nil
	a.Offset = 0
	a.Type = obj.TYPE_REG
	a.Reg = int16(rn)
	a.Name = 0

	Ostats.Ncvtreg++
}

func dumpone(f *Flow, isreg int) {
	fmt.Printf("%d:%v", f.Loop, f.Prog)
	if isreg != 0 {
851 852 853
		r := f.Data.(*Reg)
		var bit Bits
		for z := 0; z < BITS; z++ {
854 855
			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
		}
856
		if bany(&bit) {
857
			fmt.Printf("\t")
858
			if bany(&r.set) {
859 860
				fmt.Printf(" s:%v", Qconv(r.set, 0))
			}
861
			if bany(&r.use1) {
862 863
				fmt.Printf(" u1:%v", Qconv(r.use1, 0))
			}
864
			if bany(&r.use2) {
865 866
				fmt.Printf(" u2:%v", Qconv(r.use2, 0))
			}
867
			if bany(&r.refbehind) {
868 869
				fmt.Printf(" rb:%v ", Qconv(r.refbehind, 0))
			}
870
			if bany(&r.refahead) {
871 872
				fmt.Printf(" ra:%v ", Qconv(r.refahead, 0))
			}
873
			if bany(&r.calbehind) {
874 875
				fmt.Printf(" cb:%v ", Qconv(r.calbehind, 0))
			}
876
			if bany(&r.calahead) {
877 878
				fmt.Printf(" ca:%v ", Qconv(r.calahead, 0))
			}
879
			if bany(&r.regdiff) {
880 881
				fmt.Printf(" d:%v ", Qconv(r.regdiff, 0))
			}
882
			if bany(&r.act) {
883 884 885 886 887 888 889 890 891 892 893 894
				fmt.Printf(" a:%v ", Qconv(r.act, 0))
			}
		}
	}

	fmt.Printf("\n")
}

func Dumpit(str string, r0 *Flow, isreg int) {
	var r1 *Flow

	fmt.Printf("\n%s\n", str)
895
	for r := r0; r != nil; r = r.Link {
896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936
		dumpone(r, isreg)
		r1 = r.P2
		if r1 != nil {
			fmt.Printf("\tpred:")
			for ; r1 != nil; r1 = r1.P2link {
				fmt.Printf(" %.4d", uint(int(r1.Prog.Pc)))
			}
			if r.P1 != nil {
				fmt.Printf(" (and %.4d)", uint(int(r.P1.Prog.Pc)))
			} else {
				fmt.Printf(" (only)")
			}
			fmt.Printf("\n")
		}

		// Print successors if it's not just the next one
		if r.S1 != r.Link || r.S2 != nil {
			fmt.Printf("\tsucc:")
			if r.S1 != nil {
				fmt.Printf(" %.4d", uint(int(r.S1.Prog.Pc)))
			}
			if r.S2 != nil {
				fmt.Printf(" %.4d", uint(int(r.S2.Prog.Pc)))
			}
			fmt.Printf("\n")
		}
	}
}

func regopt(firstp *obj.Prog) {
	if first != 0 {
		first = 0
	}

	mergetemp(firstp)

	/*
	 * 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.
	 */
937 938
	var nreg int
	regnames := Thearch.Regnames(&nreg)
939 940

	nvar = nreg
941
	for i := 0; i < nreg; i++ {
942 943
		var_[i] = Var{}
	}
944
	for i := 0; i < nreg; i++ {
945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964
		if regnodes[i] == nil {
			regnodes[i] = newname(Lookup(regnames[i]))
		}
		var_[i].node = regnodes[i]
	}

	regbits = Thearch.Excludedregs()
	externs = zbits
	params = zbits
	consts = zbits
	addrs = zbits
	ivar = zbits
	ovar = zbits

	/*
	 * pass 1
	 * build aux data structure
	 * allocate pcs
	 * find use and set of variables
	 */
965
	g := Flowstart(firstp, func() interface{} { return new(Reg) })
966 967

	if g == nil {
968
		for i := 0; i < nvar; i++ {
969 970 971 972 973 974 975
			var_[i].node.Opt = nil
		}
		return
	}

	firstf = g.Start

976 977 978 979 980 981
	var r *Reg
	var info ProgInfo
	var p *obj.Prog
	var bit Bits
	var z int
	for f := firstf; f != nil; f = f.Link {
982 983 984 985
		p = f.Prog
		if p.As == obj.AVARDEF || p.As == obj.AVARKILL {
			continue
		}
986
		info = Thearch.Proginfo(p)
987 988 989 990 991 992 993 994 995 996 997 998 999

		// Avoid making variables for direct-called functions.
		if p.As == obj.ACALL && p.To.Type == obj.TYPE_MEM && p.To.Name == obj.NAME_EXTERN {
			continue
		}

		// from vs to doesn't matter for registers.
		r = f.Data.(*Reg)

		r.use1.b[0] |= info.Reguse | info.Regindex
		r.set.b[0] |= info.Regset

		bit = mkvar(f, &p.From)
1000
		if bany(&bit) {
1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027
			if info.Flags&LeftAddr != 0 {
				setaddrs(bit)
			}
			if info.Flags&LeftRead != 0 {
				for z = 0; z < BITS; z++ {
					r.use1.b[z] |= bit.b[z]
				}
			}
			if info.Flags&LeftWrite != 0 {
				for z = 0; z < BITS; z++ {
					r.set.b[z] |= bit.b[z]
				}
			}
		}

		// Compute used register for reg
		if info.Flags&RegRead != 0 {
			r.use1.b[0] |= Thearch.RtoB(int(p.Reg))
		}

		// Currently we never generate three register forms.
		// If we do, this will need to change.
		if p.From3.Type != obj.TYPE_NONE {
			Fatal("regopt not implemented for from3")
		}

		bit = mkvar(f, &p.To)
1028
		if bany(&bit) {
1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044
			if info.Flags&RightAddr != 0 {
				setaddrs(bit)
			}
			if info.Flags&RightRead != 0 {
				for z = 0; z < BITS; z++ {
					r.use2.b[z] |= bit.b[z]
				}
			}
			if info.Flags&RightWrite != 0 {
				for z = 0; z < BITS; z++ {
					r.set.b[z] |= bit.b[z]
				}
			}
		}
	}

1045
	for i := 0; i < nvar; i++ {
1046
		v := &var_[i]
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
		if v.addr != 0 {
			bit = blsh(uint(i))
			for z = 0; z < BITS; z++ {
				addrs.b[z] |= bit.b[z]
			}
		}

		if Debug['R'] != 0 && Debug['v'] != 0 {
			fmt.Printf("bit=%2d addr=%d et=%v w=%-2d s=%v + %d\n", i, v.addr, Econv(int(v.etype), 0), v.width, Nconv(v.node, 0), v.offset)
		}
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		Dumpit("pass1", firstf, 1)
	}

	/*
	 * pass 2
	 * find looping structure
	 */
	flowrpo(g)

	if Debug['R'] != 0 && Debug['v'] != 0 {
		Dumpit("pass2", firstf, 1)
	}

	/*
	 * pass 2.5
	 * iterate propagating fat vardef covering forward
	 * r->act records vars with a VARDEF since the last CALL.
	 * (r->act will be reused in pass 5 for something else,
	 * but we'll be done with it by then.)
	 */
1080
	active := 0
1081

1082
	for f := firstf; f != nil; f = f.Link {
1083 1084 1085 1086 1087
		f.Active = 0
		r = f.Data.(*Reg)
		r.act = zbits
	}

1088
	for f := firstf; f != nil; f = f.Link {
1089
		p = f.Prog
1090
		if p.As == obj.AVARDEF && Isfat(((p.To.Node).(*Node)).Type) && ((p.To.Node).(*Node)).Opt != nil {
1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
			active++
			walkvardef(p.To.Node.(*Node), f, active)
		}
	}

	/*
	 * pass 3
	 * iterate propagating usage
	 * 	back until flow graph is complete
	 */
1101 1102 1103
	var f1 *Flow
	var i int
	var f *Flow
1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121
loop1:
	change = 0

	for f = firstf; f != nil; f = f.Link {
		f.Active = 0
	}
	for f = firstf; f != nil; f = f.Link {
		if f.Prog.As == obj.ARET {
			prop(f, zbits, zbits)
		}
	}

	/* pick up unreachable code */
loop11:
	i = 0

	for f = firstf; f != nil; f = f1 {
		f1 = f.Link
1122
		if f1 != nil && f1.Active != 0 && f.Active == 0 {
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
			prop(f, zbits, zbits)
			i = 1
		}
	}

	if i != 0 {
		goto loop11
	}
	if change != 0 {
		goto loop1
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		Dumpit("pass3", firstf, 1)
	}

	/*
	 * pass 4
	 * iterate propagating register/variable synchrony
	 * 	forward until graph is complete
	 */
loop2:
	change = 0

	for f = firstf; f != nil; f = f.Link {
		f.Active = 0
	}
	synch(firstf, zbits)
	if change != 0 {
		goto loop2
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		Dumpit("pass4", firstf, 1)
	}

	/*
	 * pass 4.5
	 * move register pseudo-variables into regu.
	 */
1163 1164
	mask := uint64((1 << uint(nreg)) - 1)
	for f := firstf; f != nil; f = f.Link {
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
		r = f.Data.(*Reg)
		r.regu = (r.refbehind.b[0] | r.set.b[0]) & mask
		r.set.b[0] &^= mask
		r.use1.b[0] &^= mask
		r.use2.b[0] &^= mask
		r.refbehind.b[0] &^= mask
		r.refahead.b[0] &^= mask
		r.calbehind.b[0] &^= mask
		r.calahead.b[0] &^= mask
		r.regdiff.b[0] &^= mask
		r.act.b[0] &^= mask
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		Dumpit("pass4.5", firstf, 1)
	}

	/*
	 * pass 5
	 * isolate regions
	 * calculate costs (paint1)
	 */
	f = firstf

	if f != nil {
1190 1191
		r := f.Data.(*Reg)
		for z := 0; z < BITS; z++ {
1192 1193
			bit.b[z] = (r.refahead.b[z] | r.calahead.b[z]) &^ (externs.b[z] | params.b[z] | addrs.b[z] | consts.b[z])
		}
1194
		if bany(&bit) && f.Refset == 0 {
1195 1196 1197 1198 1199 1200 1201 1202
			// should never happen - all variables are preset
			if Debug['w'] != 0 {
				fmt.Printf("%v: used and not set: %v\n", f.Prog.Line(), Qconv(bit, 0))
			}
			f.Refset = 1
		}
	}

1203
	for f := firstf; f != nil; f = f.Link {
1204 1205 1206
		(f.Data.(*Reg)).act = zbits
	}
	nregion = 0
1207 1208
	var rgp *Rgn
	for f := firstf; f != nil; f = f.Link {
1209 1210 1211 1212
		r = f.Data.(*Reg)
		for z = 0; z < BITS; z++ {
			bit.b[z] = r.set.b[z] &^ (r.refahead.b[z] | r.calahead.b[z] | addrs.b[z])
		}
1213
		if bany(&bit) && f.Refset == 0 {
1214 1215 1216 1217 1218 1219 1220 1221 1222 1223
			if Debug['w'] != 0 {
				fmt.Printf("%v: set and not used: %v\n", f.Prog.Line(), Qconv(bit, 0))
			}
			f.Refset = 1
			Thearch.Excise(f)
		}

		for z = 0; z < BITS; z++ {
			bit.b[z] = LOAD(r, z) &^ (r.act.b[z] | addrs.b[z])
		}
1224
		for bany(&bit) {
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
			i = bnum(bit)
			change = 0
			paint1(f, i)
			biclr(&bit, uint(i))
			if change <= 0 {
				continue
			}
			if nregion >= NRGN {
				if Debug['R'] != 0 && Debug['v'] != 0 {
					fmt.Printf("too many regions\n")
				}
				goto brk
			}

			rgp = &region[nregion]
			rgp.enter = f
			rgp.varno = int16(i)
			rgp.cost = int16(change)
			nregion++
		}
	}

brk:
	sort.Sort(rcmp(region[:nregion]))

	if Debug['R'] != 0 && Debug['v'] != 0 {
		Dumpit("pass5", firstf, 1)
	}

	/*
	 * pass 6
	 * determine used registers (paint2)
	 * replace code (paint3)
	 */
	if Debug['R'] != 0 && Debug['v'] != 0 {
		fmt.Printf("\nregisterizing\n")
	}
1262 1263 1264
	var usedreg uint64
	var vreg uint64
	for i := 0; i < nregion; i++ {
1265 1266 1267 1268 1269 1270 1271 1272 1273
		rgp = &region[i]
		if Debug['R'] != 0 && Debug['v'] != 0 {
			fmt.Printf("region %d: cost %d varno %d enter %d\n", i, rgp.cost, rgp.varno, rgp.enter.Prog.Pc)
		}
		bit = blsh(uint(rgp.varno))
		usedreg = paint2(rgp.enter, int(rgp.varno), 0)
		vreg = allreg(usedreg, rgp)
		if rgp.regno != 0 {
			if Debug['R'] != 0 && Debug['v'] != 0 {
1274
				v := &var_[rgp.varno]
1275
				fmt.Printf("registerize %v+%d (bit=%2d et=%v) in %v usedreg=%#x vreg=%#x\n", Nconv(v.node, 0), v.offset, rgp.varno, Econv(int(v.etype), 0), obj.Rconv(int(rgp.regno)), usedreg, vreg)
1276 1277 1278 1279 1280 1281 1282 1283 1284
			}

			paint3(rgp.enter, int(rgp.varno), vreg, int(rgp.regno))
		}
	}

	/*
	 * free aux structures. peep allocates new ones.
	 */
1285
	for i := 0; i < nvar; i++ {
1286 1287 1288 1289 1290 1291 1292
		var_[i].node.Opt = nil
	}
	Flowend(g)
	firstf = nil

	if Debug['R'] != 0 && Debug['v'] != 0 {
		// Rebuild flow graph, since we inserted instructions
1293
		g := Flowstart(firstp, nil)
1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304

		firstf = g.Start
		Dumpit("pass6", firstf, 0)
		Flowend(g)
		firstf = nil
	}

	/*
	 * pass 7
	 * peep-hole on basic block
	 */
1305
	if Debug['R'] == 0 || Debug['P'] != 0 {
1306 1307 1308 1309 1310 1311
		Thearch.Peep(firstp)
	}

	/*
	 * eliminate nops
	 */
1312
	for p := firstp; p != nil; p = p.Link {
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
		for p.Link != nil && p.Link.As == obj.ANOP {
			p.Link = p.Link.Link
		}
		if p.To.Type == obj.TYPE_BRANCH {
			for p.To.U.Branch != nil && p.To.U.Branch.As == obj.ANOP {
				p.To.U.Branch = p.To.U.Branch.Link
			}
		}
	}

	if Debug['R'] != 0 {
		if Ostats.Ncvtreg != 0 || Ostats.Nspill != 0 || Ostats.Nreload != 0 || Ostats.Ndelmov != 0 || Ostats.Nvar != 0 || Ostats.Naddr != 0 || false {
			fmt.Printf("\nstats\n")
		}

		if Ostats.Ncvtreg != 0 {
			fmt.Printf("\t%4d cvtreg\n", Ostats.Ncvtreg)
		}
		if Ostats.Nspill != 0 {
			fmt.Printf("\t%4d spill\n", Ostats.Nspill)
		}
		if Ostats.Nreload != 0 {
			fmt.Printf("\t%4d reload\n", Ostats.Nreload)
		}
		if Ostats.Ndelmov != 0 {
			fmt.Printf("\t%4d delmov\n", Ostats.Ndelmov)
		}
		if Ostats.Nvar != 0 {
			fmt.Printf("\t%4d var\n", Ostats.Nvar)
		}
		if Ostats.Naddr != 0 {
			fmt.Printf("\t%4d addr\n", Ostats.Naddr)
		}

		Ostats = OptStats{}
	}
}