walk.go 84.1 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
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package gc

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

var mpzero Mpint

// The constant is known to runtime.
const (
	tmpstringbufsize = 32
)

func walk(fn *Node) {
	Curfn = fn

	if Debug['W'] != 0 {
24
		s := fmt.Sprintf("\nbefore %v", Curfn.Func.Nname.Sym)
25 26 27
		dumplist(s, Curfn.Nbody)
	}

28
	lno := int(lineno)
29 30 31

	// Final typecheck for any unused variables.
	// It's hard to be on the heap when not-used, but best to be consistent about &~PHEAP here and below.
32
	for l := fn.Func.Dcl; l != nil; l = l.Next {
33 34 35 36 37 38
		if l.N.Op == ONAME && l.N.Class&^PHEAP == PAUTO {
			typecheck(&l.N, Erv|Easgn)
		}
	}

	// Propagate the used flag for typeswitch variables up to the NONAME in it's definition.
39
	for l := fn.Func.Dcl; l != nil; l = l.Next {
40 41
		if l.N.Op == ONAME && l.N.Class&^PHEAP == PAUTO && l.N.Name.Defn != nil && l.N.Name.Defn.Op == OTYPESW && l.N.Used {
			l.N.Name.Defn.Left.Used = true
42 43 44
		}
	}

45
	for l := fn.Func.Dcl; l != nil; l = l.Next {
46
		if l.N.Op != ONAME || l.N.Class&^PHEAP != PAUTO || l.N.Sym.Name[0] == '&' || l.N.Used {
47 48
			continue
		}
49 50
		if defn := l.N.Name.Defn; defn != nil && defn.Op == OTYPESW {
			if defn.Left.Used {
51 52
				continue
			}
53
			lineno = defn.Left.Lineno
54
			Yyerror("%v declared and not used", l.N.Sym)
55
			defn.Left.Used = true // suppress repeats
56 57
		} else {
			lineno = l.N.Lineno
58
			Yyerror("%v declared and not used", l.N.Sym)
59 60 61 62 63 64 65 66 67
		}
	}

	lineno = int32(lno)
	if nerrors != 0 {
		return
	}
	walkstmtlist(Curfn.Nbody)
	if Debug['W'] != 0 {
68
		s := fmt.Sprintf("after walk %v", Curfn.Func.Nname.Sym)
69 70 71 72
		dumplist(s, Curfn.Nbody)
	}

	heapmoves()
73
	if Debug['W'] != 0 && Curfn.Func.Enter != nil {
74
		s := fmt.Sprintf("enter %v", Curfn.Func.Nname.Sym)
75
		dumplist(s, Curfn.Func.Enter)
76 77 78 79 80 81 82 83 84
	}
}

func walkstmtlist(l *NodeList) {
	for ; l != nil; l = l.Next {
		walkstmt(&l.N)
	}
}

85
func samelist(a *NodeList, b *NodeList) bool {
86
	for ; a != nil && b != nil; a, b = a.Next, b.Next {
87
		if a.N != b.N {
88
			return false
89 90
		}
	}
91
	return a == b
92 93
}

94
func paramoutheap(fn *Node) bool {
95
	for l := fn.Func.Dcl; l != nil; l = l.Next {
96 97 98
		switch l.N.Class {
		case PPARAMOUT,
			PPARAMOUT | PHEAP:
99
			return l.N.Addrtaken
100 101 102 103

			// stop early - parameters are over
		case PAUTO,
			PAUTO | PHEAP:
104
			return false
105 106 107
		}
	}

108
	return false
109 110 111 112 113 114 115 116
}

// adds "adjust" to all the argument locations for the call n.
// n must be a defer or go node that has already been walked.
func adjustargs(n *Node, adjust int) {
	var arg *Node
	var lhs *Node

117 118
	callfunc := n.Left
	for args := callfunc.List; args != nil; args = args.Next {
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
		arg = args.N
		if arg.Op != OAS {
			Yyerror("call arg not assignment")
		}
		lhs = arg.Left
		if lhs.Op == ONAME {
			// This is a temporary introduced by reorder1.
			// The real store to the stack appears later in the arg list.
			continue
		}

		if lhs.Op != OINDREG {
			Yyerror("call argument store does not use OINDREG")
		}

		// can't really check this in machine-indep code.
		//if(lhs->val.u.reg != D_SP)
		//      yyerror("call arg assign not indreg(SP)");
		lhs.Xoffset += int64(adjust)
	}
}

func walkstmt(np **Node) {
142
	n := *np
143 144 145 146 147 148 149 150 151 152 153 154 155 156
	if n == nil {
		return
	}
	if n.Dodata == 2 { // don't walk, generated by anylit.
		return
	}

	setlineno(n)

	walkstmtlist(n.Ninit)

	switch n.Op {
	default:
		if n.Op == ONAME {
157
			Yyerror("%v is not a top level statement", n.Sym)
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
		} else {
			Yyerror("%v is not a top level statement", Oconv(int(n.Op), 0))
		}
		Dump("nottop", n)

	case OAS,
		OASOP,
		OAS2,
		OAS2DOTTYPE,
		OAS2RECV,
		OAS2FUNC,
		OAS2MAPR,
		OCLOSE,
		OCOPY,
		OCALLMETH,
		OCALLINTER,
		OCALL,
		OCALLFUNC,
		ODELETE,
		OSEND,
		OPRINT,
		OPRINTN,
		OPANIC,
		OEMPTY,
182 183
		ORECOVER,
		OGETG:
184
		if n.Typecheck == 0 {
185
			Fatalf("missing typecheck: %v", Nconv(n, obj.FmtSign))
186
		}
187
		init := n.Ninit
188 189 190 191 192 193 194 195 196 197 198
		n.Ninit = nil
		walkexpr(&n, &init)
		addinit(&n, init)
		if (*np).Op == OCOPY && n.Op == OCONVNOP {
			n.Op = OEMPTY // don't leave plain values as statements.
		}

		// special case for a receive where we throw away
	// the value received.
	case ORECV:
		if n.Typecheck == 0 {
199
			Fatalf("missing typecheck: %v", Nconv(n, obj.FmtSign))
200
		}
201
		init := n.Ninit
202 203 204 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
		n.Ninit = nil

		walkexpr(&n.Left, &init)
		n = mkcall1(chanfn("chanrecv1", 2, n.Left.Type), nil, &init, typename(n.Left.Type), n.Left, nodnil())
		walkexpr(&n, &init)

		addinit(&n, init)

	case OBREAK,
		ODCL,
		OCONTINUE,
		OFALL,
		OGOTO,
		OLABEL,
		ODCLCONST,
		ODCLTYPE,
		OCHECKNIL,
		OVARKILL:
		break

	case OBLOCK:
		walkstmtlist(n.List)

	case OXCASE:
		Yyerror("case statement out of place")
		n.Op = OCASE
		fallthrough

	case OCASE:
		walkstmt(&n.Right)

	case ODEFER:
234
		hasdefer = true
235
		switch n.Left.Op {
236
		case OPRINT, OPRINTN:
237 238 239
			walkprintfunc(&n.Left, &n.Ninit)

		case OCOPY:
240
			n.Left = copyany(n.Left, &n.Ninit, true)
241 242 243 244 245 246 247 248 249

		default:
			walkexpr(&n.Left, &n.Ninit)
		}

		// make room for size & fn arguments.
		adjustargs(n, 2*Widthptr)

	case OFOR:
250 251 252 253 254 255
		if n.Left != nil {
			walkstmtlist(n.Left.Ninit)
			init := n.Left.Ninit
			n.Left.Ninit = nil
			walkexpr(&n.Left, &init)
			addinit(&n.Left, init)
256 257
		}

258
		walkstmt(&n.Right)
259 260 261
		walkstmtlist(n.Nbody)

	case OIF:
262
		walkexpr(&n.Left, &n.Ninit)
263
		walkstmtlist(n.Nbody)
264
		walkstmtlist(n.Rlist)
265 266 267

	case OPROC:
		switch n.Left.Op {
268
		case OPRINT, OPRINTN:
269 270 271
			walkprintfunc(&n.Left, &n.Ninit)

		case OCOPY:
272
			n.Left = copyany(n.Left, &n.Ninit, true)
273 274 275 276 277 278 279 280 281 282 283 284 285

		default:
			walkexpr(&n.Left, &n.Ninit)
		}

		// make room for size & fn arguments.
		adjustargs(n, 2*Widthptr)

	case ORETURN:
		walkexprlist(n.List, &n.Ninit)
		if n.List == nil {
			break
		}
286
		if (Curfn.Type.Outnamed && count(n.List) > 1) || paramoutheap(Curfn) {
287 288
			// assign to the function out parameters,
			// so that reorder3 can fix up conflicts
Russ Cox's avatar
Russ Cox committed
289
			var rl *NodeList
290

291
			var cl Class
292
			for ll := Curfn.Func.Dcl; ll != nil; ll = ll.Next {
293
				cl = ll.N.Class &^ PHEAP
294 295 296 297 298 299 300 301
				if cl == PAUTO {
					break
				}
				if cl == PPARAMOUT {
					rl = list(rl, ll.N)
				}
			}

302
			if samelist(rl, n.List) {
303 304 305 306 307 308 309 310
				// special return in disguise
				n.List = nil

				break
			}

			if count(n.List) == 1 && count(rl) > 1 {
				// OAS2FUNC in disguise
311
				f := n.List.N
312 313

				if f.Op != OCALLFUNC && f.Op != OCALLMETH && f.Op != OCALLINTER {
314
					Fatalf("expected return of call, have %v", f)
315
				}
316
				n.List = concat(list1(f), ascompatet(n.Op, rl, &f.Type, 0, &n.Ninit))
317 318 319 320 321 322
				break
			}

			// move function calls out, to make reorder3's job easier.
			walkexprlistsafe(n.List, &n.Ninit)

323
			ll := ascompatee(n.Op, rl, n.List, &n.Ninit)
324 325 326 327
			n.List = reorder3(ll)
			break
		}

328
		ll := ascompatte(n.Op, nil, false, Getoutarg(Curfn.Type), n.List, 1, &n.Ninit)
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
		n.List = ll

	case ORETJMP:
		break

	case OSELECT:
		walkselect(n)

	case OSWITCH:
		walkswitch(n)

	case ORANGE:
		walkrange(n)

	case OXFALL:
		Yyerror("fallthrough statement out of place")
		n.Op = OFALL
	}

	if n.Op == ONAME {
349
		Fatalf("walkstmt ended up with name: %v", Nconv(n, obj.FmtSign))
350 351 352 353 354
	}

	*np = n
}

355 356 357 358 359 360 361 362 363 364 365
func isSmallMakeSlice(n *Node) bool {
	if n.Op != OMAKESLICE {
		return false
	}
	l := n.Left
	r := n.Right
	if r == nil {
		r = l
	}
	t := n.Type

366
	return Smallintconst(l) && Smallintconst(r) && (t.Type.Width == 0 || Mpgetfix(r.Val().U.(*Mpint)) < (1<<16)/t.Type.Width)
367 368
}

369 370 371 372 373
// walk the whole tree of the body of an
// expression or simple statement.
// the types expressions are calculated.
// compile-time constants are evaluated.
// complex side effects like statements are appended to init
374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
func walkexprlist(l *NodeList, init **NodeList) {
	for ; l != nil; l = l.Next {
		walkexpr(&l.N, init)
	}
}

func walkexprlistsafe(l *NodeList, init **NodeList) {
	for ; l != nil; l = l.Next {
		l.N = safeexpr(l.N, init)
		walkexpr(&l.N, init)
	}
}

func walkexprlistcheap(l *NodeList, init **NodeList) {
	for ; l != nil; l = l.Next {
		l.N = cheapexpr(l.N, init)
		walkexpr(&l.N, init)
	}
}

func walkexpr(np **Node, init **NodeList) {
395
	n := *np
396 397 398 399 400 401 402 403 404

	if n == nil {
		return
	}

	if init == &n.Ninit {
		// not okay to use n->ninit when walking n,
		// because we might replace n with some other node
		// and would lose the init list.
405
		Fatalf("walkexpr init == &n->ninit")
406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
	}

	if n.Ninit != nil {
		walkstmtlist(n.Ninit)
		*init = concat(*init, n.Ninit)
		n.Ninit = nil
	}

	// annoying case - not typechecked
	if n.Op == OKEY {
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)
		return
	}

421
	lno := setlineno(n)
422 423 424 425 426 427

	if Debug['w'] > 1 {
		Dump("walk-before", n)
	}

	if n.Typecheck != 1 {
428
		Fatalf("missed typecheck: %v\n", Nconv(n, obj.FmtSign))
429 430
	}

431
opswitch:
432 433 434
	switch n.Op {
	default:
		Dump("walk", n)
435
		Fatalf("walkexpr: switch 1 unknown op %v", Nconv(n, obj.FmtShort|obj.FmtSign))
436 437 438 439 440

	case OTYPE,
		ONONAME,
		OINDREG,
		OEMPTY,
441 442
		OPARAM,
		OGETG:
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 471 472 473 474 475

	case ONOT,
		OMINUS,
		OPLUS,
		OCOM,
		OREAL,
		OIMAG,
		ODOTMETH,
		ODOTINTER:
		walkexpr(&n.Left, init)

	case OIND:
		walkexpr(&n.Left, init)

	case ODOT:
		usefield(n)
		walkexpr(&n.Left, init)

	case ODOTPTR:
		usefield(n)
		if n.Op == ODOTPTR && n.Left.Type.Type.Width == 0 {
			// No actual copy will be generated, so emit an explicit nil check.
			n.Left = cheapexpr(n.Left, init)

			checknil(n.Left, init)
		}

		walkexpr(&n.Left, init)

	case OEFACE:
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)

476
	case OSPTR, OITAB:
477 478
		walkexpr(&n.Left, init)

479
	case OLEN, OCAP:
480 481 482 483
		walkexpr(&n.Left, init)

		// replace len(*[10]int) with 10.
		// delayed until now to preserve side effects.
484
		t := n.Left.Type
485

486
		if Isptr[t.Etype] {
487 488
			t = t.Type
		}
489
		if Isfixedarray(t) {
490 491 492 493 494
			safeexpr(n.Left, init)
			Nodconst(n, n.Type, t.Bound)
			n.Typecheck = 1
		}

495
	case OLSH, ORSH:
496 497
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)
498
		t := n.Left.Type
499 500
		n.Bounded = bounded(n.Right, 8*t.Width)
		if Debug['m'] != 0 && n.Etype != 0 && !Isconst(n.Right, CTINT) {
501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
			Warn("shift bounds check elided")
		}

		// Use results from call expression as arguments for complex.
	case OAND,
		OSUB,
		OHMUL,
		OLT,
		OLE,
		OGE,
		OGT,
		OADD,
		OCOMPLEX,
		OLROT:
		if n.Op == OCOMPLEX && n.Left == nil && n.Right == nil {
			n.Left = n.List.N
			n.Right = n.List.Next.N
		}

		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)

523
	case OOR, OXOR:
524 525 526 527
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)
		walkrotate(&n)

528
	case OEQ, ONE:
529 530 531 532 533 534 535 536
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)

		// Disable safemode while compiling this code: the code we
		// generate internally can refer to unsafe.Pointer.
		// In this case it can happen if we need to generate an ==
		// for a struct containing a reflect.Value, which itself has
		// an unexported field of type unsafe.Pointer.
537
		old_safemode := safemode
538 539 540 541 542

		safemode = 0
		walkcompare(&n, init)
		safemode = old_safemode

543
	case OANDAND, OOROR:
544 545
		walkexpr(&n.Left, init)

546 547 548
		// cannot put side effects from n.Right on init,
		// because they cannot run before n.Left is checked.
		// save elsewhere and store on the eventual n.Right.
Russ Cox's avatar
Russ Cox committed
549
		var ll *NodeList
550 551 552 553

		walkexpr(&n.Right, &ll)
		addinit(&n.Right, ll)

554
	case OPRINT, OPRINTN:
555 556 557 558 559 560 561 562 563 564
		walkexprlist(n.List, init)
		n = walkprint(n, init)

	case OPANIC:
		n = mkcall("gopanic", nil, init, n.Left)

	case ORECOVER:
		n = mkcall("gorecover", n.Type, init, Nod(OADDR, nodfp, nil))

	case OLITERAL:
565
		n.Addable = true
566

567
	case OCLOSUREVAR, OCFUNC:
568
		n.Addable = true
569 570

	case ONAME:
571
		if n.Class&PHEAP == 0 && n.Class != PPARAMREF {
572
			n.Addable = true
573 574 575
		}

	case OCALLINTER:
576
		t := n.Left.Type
577
		if n.List != nil && n.List.N.Op == OAS {
578
			break
579 580 581
		}
		walkexpr(&n.Left, init)
		walkexprlist(n.List, init)
582
		ll := ascompatte(n.Op, n, n.Isddd, getinarg(t), n.List, 0, init)
583 584 585 586 587 588 589
		n.List = reorder1(ll)

	case OCALLFUNC:
		if n.Left.Op == OCLOSURE {
			// Transform direct call of a closure to call of a normal function.
			// transformclosure already did all preparation work.

590 591
			// Prepend captured variables to argument list.
			n.List = concat(n.Left.Func.Enter, n.List)
592

593
			n.Left.Func.Enter = nil
594 595

			// Replace OCLOSURE with ONAME/PFUNC.
596
			n.Left = n.Left.Func.Closure.Func.Nname
597 598 599 600

			// Update type of OCALLFUNC node.
			// Output arguments had not changed, but their offsets could.
			if n.Left.Type.Outtuple == 1 {
601
				t := getoutargx(n.Left.Type).Type
602 603 604 605 606 607 608 609 610
				if t.Etype == TFIELD {
					t = t.Type
				}
				n.Type = t
			} else {
				n.Type = getoutargx(n.Left.Type)
			}
		}

611
		t := n.Left.Type
612
		if n.List != nil && n.List.N.Op == OAS {
613
			break
614 615 616 617 618
		}

		walkexpr(&n.Left, init)
		walkexprlist(n.List, init)

619 620
		if n.Left.Op == ONAME && n.Left.Sym.Name == "Sqrt" && n.Left.Sym.Pkg.Path == "math" {
			switch Thearch.Thechar {
621
			case '5', '6', '7':
622 623 624
				n.Op = OSQRT
				n.Left = n.List.N
				n.List = nil
625
				break opswitch
626 627 628
			}
		}

629
		ll := ascompatte(n.Op, n, n.Isddd, getinarg(t), n.List, 0, init)
630 631 632
		n.List = reorder1(ll)

	case OCALLMETH:
633
		t := n.Left.Type
634
		if n.List != nil && n.List.N.Op == OAS {
635
			break
636 637 638
		}
		walkexpr(&n.Left, init)
		walkexprlist(n.List, init)
639 640
		ll := ascompatte(n.Op, n, false, getthis(t), list1(n.Left.Left), 0, init)
		lr := ascompatte(n.Op, n, n.Isddd, getinarg(t), n.List, 0, init)
641 642 643 644 645 646 647 648 649 650 651 652
		ll = concat(ll, lr)
		n.Left.Left = nil
		ullmancalc(n.Left)
		n.List = reorder1(ll)

	case OAS:
		*init = concat(*init, n.Ninit)
		n.Ninit = nil

		walkexpr(&n.Left, init)
		n.Left = safeexpr(n.Left, init)

653
		if oaslit(n, init) {
654
			break
655 656
		}

657
		if n.Right == nil || iszero(n.Right) && !instrumenting {
658
			break
659 660 661 662 663 664 665
		}

		switch n.Right.Op {
		default:
			walkexpr(&n.Right, init)

		case ODOTTYPE:
666 667 668
			// TODO(rsc): The Isfat is for consistency with componentgen and orderexpr.
			// It needs to be removed in all three places.
			// That would allow inlining x.(struct{*int}) the same as x.(*int).
669
			if isdirectiface(n.Right.Type) && !Isfat(n.Right.Type) && !instrumenting {
670 671 672 673 674
				// handled directly during cgen
				walkexpr(&n.Right, init)
				break
			}

675
			// x = i.(T); n.Left is x, n.Right.Left is i.
676
			// orderstmt made sure x is addressable.
677 678
			walkexpr(&n.Right.Left, init)

679 680
			n1 := Nod(OADDR, n.Left, nil)
			r := n.Right // i.(T)
681

682 683 684 685
			if Debug_typeassert > 0 {
				Warn("type assertion not inlined")
			}

686
			buf := "assert" + type2IET(r.Left.Type) + "2" + type2IET(r.Type)
687
			fn := syslook(buf, 1)
688
			substArgTypes(fn, r.Left.Type, r.Type)
689 690 691

			n = mkcall1(fn, nil, init, typename(r.Type), r.Left, n1)
			walkexpr(&n, init)
692
			break opswitch
693 694

		case ORECV:
695
			// x = <-c; n.Left is x, n.Right.Left is c.
696
			// orderstmt made sure x is addressable.
697 698
			walkexpr(&n.Right.Left, init)

699 700
			n1 := Nod(OADDR, n.Left, nil)
			r := n.Right.Left // the channel
701 702
			n = mkcall1(chanfn("chanrecv1", 2, r.Type), nil, init, typename(r.Type), r, n1)
			walkexpr(&n, init)
703
			break opswitch
704 705 706 707 708 709 710 711 712 713 714 715 716

		case OAPPEND:
			// x = append(...)
			r := n.Right
			if r.Isddd {
				r = appendslice(r, init) // also works for append(slice, string).
			} else {
				r = walkappend(r, init, n)
			}
			n.Right = r
			if r.Op == OAPPEND {
				// Left in place for back end.
				// Do not add a new write barrier.
717
				break opswitch
718 719 720
			}
			// Otherwise, lowered for race detector.
			// Treat as ordinary assignment.
721 722 723
		}

		if n.Left != nil && n.Right != nil {
724
			r := convas(Nod(OAS, n.Left, n.Right), init)
725 726 727 728 729 730 731 732 733 734
			r.Dodata = n.Dodata
			n = r
			n = applywritebarrier(n, init)
		}

	case OAS2:
		*init = concat(*init, n.Ninit)
		n.Ninit = nil
		walkexprlistsafe(n.List, init)
		walkexprlistsafe(n.Rlist, init)
735
		ll := ascompatee(OAS, n.List, n.Rlist, init)
736
		ll = reorder3(ll)
737
		for lr := ll; lr != nil; lr = lr.Next {
738 739 740 741 742 743 744 745 746
			lr.N = applywritebarrier(lr.N, init)
		}
		n = liststmt(ll)

		// a,b,... = fn()
	case OAS2FUNC:
		*init = concat(*init, n.Ninit)

		n.Ninit = nil
747
		r := n.Rlist.N
748 749 750
		walkexprlistsafe(n.List, init)
		walkexpr(&r, init)

751
		ll := ascompatet(n.Op, n.List, &r.Type, 0, init)
752
		for lr := ll; lr != nil; lr = lr.Next {
753 754 755 756 757 758 759 760 761 762
			lr.N = applywritebarrier(lr.N, init)
		}
		n = liststmt(concat(list1(r), ll))

		// x, y = <-c
	// orderstmt made sure x is addressable.
	case OAS2RECV:
		*init = concat(*init, n.Ninit)

		n.Ninit = nil
763
		r := n.Rlist.N
764 765
		walkexprlistsafe(n.List, init)
		walkexpr(&r.Left, init)
766
		var n1 *Node
767 768 769 770 771 772
		if isblank(n.List.N) {
			n1 = nodnil()
		} else {
			n1 = Nod(OADDR, n.List.N, nil)
		}
		n1.Etype = 1 // addr does not escape
773
		fn := chanfn("chanrecv2", 2, r.Left.Type)
774 775 776 777 778 779 780 781 782
		r = mkcall1(fn, n.List.Next.N.Type, init, typename(r.Left.Type), r.Left, n1)
		n = Nod(OAS, n.List.Next.N, r)
		typecheck(&n, Etop)

		// a,b = m[i];
	case OAS2MAPR:
		*init = concat(*init, n.Ninit)

		n.Ninit = nil
783
		r := n.Rlist.N
784 785 786
		walkexprlistsafe(n.List, init)
		walkexpr(&r.Left, init)
		walkexpr(&r.Right, init)
787 788
		t := r.Left.Type
		p := ""
789 790
		if t.Type.Width <= 128 { // Check ../../runtime/hashmap.go:maxValueSize before changing.
			switch Simsimtype(t.Down) {
791
			case TINT32, TUINT32:
792 793
				p = "mapaccess2_fast32"

794
			case TINT64, TUINT64:
795 796 797 798 799 800 801
				p = "mapaccess2_fast64"

			case TSTRING:
				p = "mapaccess2_faststr"
			}
		}

802
		var key *Node
803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818
		if p != "" {
			// fast versions take key by value
			key = r.Right
		} else {
			// standard version takes key by reference
			// orderexpr made sure key is addressable.
			key = Nod(OADDR, r.Right, nil)

			p = "mapaccess2"
		}

		// from:
		//   a,b = m[i]
		// to:
		//   var,b = mapaccess2*(t, m, i)
		//   a = *var
819
		a := n.List.N
820

821
		fn := mapfn(p, t)
822 823 824 825 826 827 828 829 830 831 832 833 834
		r = mkcall1(fn, getoutargx(fn.Type), init, typename(t), r.Left, key)

		// mapaccess2* returns a typed bool, but due to spec changes,
		// the boolean result of i.(T) is now untyped so we make it the
		// same type as the variable on the lhs.
		if !isblank(n.List.Next.N) {
			r.Type.Type.Down.Type = n.List.Next.N.Type
		}
		n.Rlist = list1(r)
		n.Op = OAS2FUNC

		// don't generate a = *var if a is _
		if !isblank(a) {
835
			var_ := temp(Ptrto(t.Type))
836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
			var_.Typecheck = 1
			n.List.N = var_
			walkexpr(&n, init)
			*init = list(*init, n)
			n = Nod(OAS, a, Nod(OIND, var_, nil))
		}

		typecheck(&n, Etop)
		walkexpr(&n, init)

		// TODO: ptr is always non-nil, so disable nil check for this OIND op.

	case ODELETE:
		*init = concat(*init, n.Ninit)
		n.Ninit = nil
851 852
		map_ := n.List.N
		key := n.List.Next.N
853 854 855 856 857 858
		walkexpr(&map_, init)
		walkexpr(&key, init)

		// orderstmt made sure key is addressable.
		key = Nod(OADDR, key, nil)

859
		t := map_.Type
860 861 862
		n = mkcall1(mapfndel("mapdelete", t), nil, init, typename(t), map_, key)

	case OAS2DOTTYPE:
863 864 865 866
		e := n.Rlist.N // i.(T)
		// TODO(rsc): The Isfat is for consistency with componentgen and orderexpr.
		// It needs to be removed in all three places.
		// That would allow inlining x.(struct{*int}) the same as x.(*int).
867
		if isdirectiface(e.Type) && !Isfat(e.Type) && !instrumenting {
868 869 870
			// handled directly during gen.
			walkexprlistsafe(n.List, init)
			walkexpr(&e.Left, init)
871
			break
872 873 874 875
		}

		// res, ok = i.(T)
		// orderstmt made sure a is addressable.
876 877 878
		*init = concat(*init, n.Ninit)
		n.Ninit = nil

879 880 881 882
		walkexprlistsafe(n.List, init)
		walkexpr(&e.Left, init)
		t := e.Type    // T
		from := e.Left // i
883

884 885 886 887
		oktype := Types[TBOOL]
		ok := n.List.Next.N
		if !isblank(ok) {
			oktype = ok.Type
888
		}
889

890 891
		fromKind := type2IET(from.Type)
		toKind := type2IET(t)
892 893 894 895 896 897 898 899 900 901 902 903 904 905 906

		// Avoid runtime calls in a few cases of the form _, ok := i.(T).
		// This is faster and shorter and allows the corresponding assertX2X2
		// routines to skip nil checks on their last argument.
		if isblank(n.List.N) {
			var fast *Node
			switch {
			case fromKind == "E" && toKind == "T":
				tab := Nod(OITAB, from, nil) // type:eface::tab:iface
				typ := Nod(OCONVNOP, typename(t), nil)
				typ.Type = Ptrto(Types[TUINTPTR])
				fast = Nod(OEQ, tab, typ)
			case fromKind == "I" && toKind == "E",
				fromKind == "E" && toKind == "E":
				tab := Nod(OITAB, from, nil)
907
				fast = Nod(ONE, nodnil(), tab)
908 909
			}
			if fast != nil {
910 911 912
				if Debug_typeassert > 0 {
					Warn("type assertion (ok only) inlined")
				}
913 914
				n = Nod(OAS, ok, fast)
				typecheck(&n, Etop)
915
				break
916 917 918
			}
		}

919 920 921 922 923
		var resptr *Node // &res
		if isblank(n.List.N) {
			resptr = nodnil()
		} else {
			resptr = Nod(OADDR, n.List.N, nil)
924
		}
925
		resptr.Etype = 1 // addr does not escape
926

927 928 929
		if Debug_typeassert > 0 {
			Warn("type assertion not inlined")
		}
930
		buf := "assert" + fromKind + "2" + toKind + "2"
931
		fn := syslook(buf, 1)
932 933 934
		substArgTypes(fn, from.Type, t)
		call := mkcall1(fn, oktype, init, typename(t), from, resptr)
		n = Nod(OAS, ok, call)
935 936
		typecheck(&n, Etop)

937 938
	case ODOTTYPE, ODOTTYPE2:
		if !isdirectiface(n.Type) || Isfat(n.Type) {
939
			Fatalf("walkexpr ODOTTYPE") // should see inside OAS only
940 941
		}
		walkexpr(&n.Left, init)
942 943 944 945 946

	case OCONVIFACE:
		walkexpr(&n.Left, init)

		// Optimize convT2E as a two-word copy when T is pointer-shaped.
947
		if isnilinter(n.Type) && isdirectiface(n.Left.Type) {
948
			l := Nod(OEFACE, typename(n.Left.Type), n.Left)
949 950 951
			l.Type = n.Type
			l.Typecheck = n.Typecheck
			n = l
952
			break
953 954
		}

955 956 957 958 959
		// Build name of function: convI2E etc.
		// Not all names are possible
		// (e.g., we'll never generate convE2E or convE2I).
		buf := "conv" + type2IET(n.Left.Type) + "2" + type2IET(n.Type)
		fn := syslook(buf, 1)
Russ Cox's avatar
Russ Cox committed
960
		var ll *NodeList
961
		if !Isinter(n.Left.Type) {
962 963
			ll = list(ll, typename(n.Left.Type))
		}
964
		if !isnilinter(n.Type) {
965 966
			ll = list(ll, typename(n.Type))
		}
967
		if !Isinter(n.Left.Type) && !isnilinter(n.Type) {
968
			sym := Pkglookup(Tconv(n.Left.Type, obj.FmtLeft)+"."+Tconv(n.Type, obj.FmtLeft), itabpkg)
969
			if sym.Def == nil {
970
				l := Nod(ONAME, nil, nil)
971 972
				l.Sym = sym
				l.Type = Ptrto(Types[TUINT8])
973
				l.Addable = true
974 975 976 977 978 979
				l.Class = PEXTERN
				l.Xoffset = 0
				sym.Def = l
				ggloblsym(sym, int32(Widthptr), obj.DUPOK|obj.NOPTR)
			}

980
			l := Nod(OADDR, sym.Def, nil)
981
			l.Addable = true
982 983
			ll = list(ll, l)

984
			if isdirectiface(n.Left.Type) {
985 986 987 988 989 990 991 992 993
				// For pointer types, we can make a special form of optimization
				//
				// These statements are put onto the expression init list:
				// 	Itab *tab = atomicloadtype(&cache);
				// 	if(tab == nil)
				// 		tab = typ2Itab(type, itype, &cache);
				//
				// The CONVIFACE expression is replaced with this:
				// 	OEFACE{tab, ptr};
994
				l := temp(Ptrto(Types[TUINT8]))
995

996
				n1 := Nod(OAS, l, sym.Def)
997 998 999
				typecheck(&n1, Etop)
				*init = list(*init, n1)

1000
				fn := syslook("typ2Itab", 1)
1001 1002 1003 1004 1005
				n1 = Nod(OCALL, fn, nil)
				n1.List = ll
				typecheck(&n1, Erv)
				walkexpr(&n1, init)

1006
				n2 := Nod(OIF, nil, nil)
1007
				n2.Left = Nod(OEQ, l, nodnil())
1008 1009 1010 1011 1012 1013 1014 1015 1016
				n2.Nbody = list1(Nod(OAS, l, n1))
				n2.Likely = -1
				typecheck(&n2, Etop)
				*init = list(*init, n2)

				l = Nod(OEFACE, l, n.Left)
				l.Typecheck = n.Typecheck
				l.Type = n.Type
				n = l
1017
				break
1018 1019 1020
			}
		}

1021
		if Isinter(n.Left.Type) {
1022 1023 1024
			ll = list(ll, n.Left)
		} else {
			// regular types are passed by reference to avoid C vararg calls
1025
			// orderexpr arranged for n.Left to be a temporary for all
1026 1027 1028 1029
			// the conversions it could see. comparison of an interface
			// with a non-interface, especially in a switch on interface value
			// with non-interface cases, is not visible to orderstmt, so we
			// have to fall back on allocating a temp here.
1030
			if islvalue(n.Left) {
1031 1032 1033 1034
				ll = list(ll, Nod(OADDR, n.Left, nil))
			} else {
				ll = list(ll, Nod(OADDR, copyexpr(n.Left, n.Left.Type, init), nil))
			}
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046
			dowidth(n.Left.Type)
			r := nodnil()
			if n.Esc == EscNone && n.Left.Type.Width <= 1024 {
				// Allocate stack buffer for value stored in interface.
				r = temp(n.Left.Type)
				r = Nod(OAS, r, nil) // zero temp
				typecheck(&r, Etop)
				*init = list(*init, r)
				r = Nod(OADDR, r.Left, nil)
				typecheck(&r, Erv)
			}
			ll = list(ll, r)
1047 1048
		}

1049 1050 1051 1052 1053
		if !Isinter(n.Left.Type) {
			substArgTypes(fn, n.Left.Type, n.Left.Type, n.Type)
		} else {
			substArgTypes(fn, n.Left.Type, n.Type)
		}
1054 1055 1056 1057 1058 1059
		dowidth(fn.Type)
		n = Nod(OCALL, fn, nil)
		n.List = ll
		typecheck(&n, Erv)
		walkexpr(&n, init)

1060
	case OCONV, OCONVNOP:
1061
		if Thearch.Thechar == '5' {
1062
			if Isfloat[n.Left.Type.Etype] {
1063 1064
				if n.Type.Etype == TINT64 {
					n = mkcall("float64toint64", n.Type, init, conv(n.Left, Types[TFLOAT64]))
1065
					break
1066 1067 1068 1069
				}

				if n.Type.Etype == TUINT64 {
					n = mkcall("float64touint64", n.Type, init, conv(n.Left, Types[TFLOAT64]))
1070
					break
1071 1072 1073
				}
			}

1074
			if Isfloat[n.Type.Etype] {
1075 1076
				if n.Left.Type.Etype == TINT64 {
					n = mkcall("int64tofloat64", n.Type, init, conv(n.Left, Types[TINT64]))
1077
					break
1078 1079 1080 1081
				}

				if n.Left.Type.Etype == TUINT64 {
					n = mkcall("uint64tofloat64", n.Type, init, conv(n.Left, Types[TUINT64]))
1082
					break
1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
				}
			}
		}

		walkexpr(&n.Left, init)

	case OANDNOT:
		walkexpr(&n.Left, init)
		n.Op = OAND
		n.Right = Nod(OCOM, n.Right, nil)
		typecheck(&n.Right, Erv)
		walkexpr(&n.Right, init)

	case OMUL:
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)
		walkmul(&n, init)

1101
	case ODIV, OMOD:
1102 1103 1104
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)

1105
		// rewrite complex div into function call.
1106
		et := n.Left.Type.Etype
1107

1108
		if Iscomplex[et] && n.Op == ODIV {
1109
			t := n.Type
1110 1111
			n = mkcall("complex128div", Types[TCOMPLEX128], init, conv(n.Left, Types[TCOMPLEX128]), conv(n.Right, Types[TCOMPLEX128]))
			n = conv(n, t)
1112
			break
1113 1114 1115
		}

		// Nothing to do for float divisions.
1116
		if Isfloat[et] {
1117
			break
1118 1119 1120 1121 1122
		}

		// Try rewriting as shifts or magic multiplies.
		walkdiv(&n, init)

1123 1124
		// rewrite 64-bit div and mod into function calls
		// on 32-bit architectures.
1125
		switch n.Op {
1126
		case OMOD, ODIV:
1127
			if Widthreg >= 8 || (et != TUINT64 && et != TINT64) {
1128
				break opswitch
1129
			}
1130
			var fn string
1131
			if et == TINT64 {
1132
				fn = "int64"
1133
			} else {
1134
				fn = "uint64"
1135 1136
			}
			if n.Op == ODIV {
1137
				fn += "div"
1138
			} else {
1139
				fn += "mod"
1140
			}
1141
			n = mkcall(fn, n.Type, init, conv(n.Left, Types[et]), conv(n.Right, Types[et]))
1142 1143 1144 1145 1146 1147 1148
		}

	case OINDEX:
		walkexpr(&n.Left, init)

		// save the original node for bounds checking elision.
		// If it was a ODIV/OMOD walk might rewrite it.
1149
		r := n.Right
1150 1151 1152 1153 1154

		walkexpr(&n.Right, init)

		// if range of type cannot exceed static array bound,
		// disable bounds check.
1155
		if n.Bounded {
1156
			break
1157
		}
1158
		t := n.Left.Type
1159
		if t != nil && Isptr[t.Etype] {
1160 1161
			t = t.Type
		}
1162 1163 1164
		if Isfixedarray(t) {
			n.Bounded = bounded(r, t.Bound)
			if Debug['m'] != 0 && n.Bounded && !Isconst(n.Right, CTINT) {
1165 1166
				Warn("index bounds check elided")
			}
1167
			if Smallintconst(n.Right) && !n.Bounded {
1168 1169
				Yyerror("index out of bounds")
			}
1170
		} else if Isconst(n.Left, CTSTR) {
1171
			n.Bounded = bounded(r, int64(len(n.Left.Val().U.(string))))
1172
			if Debug['m'] != 0 && n.Bounded && !Isconst(n.Right, CTINT) {
1173 1174
				Warn("index bounds check elided")
			}
1175 1176
			if Smallintconst(n.Right) {
				if !n.Bounded {
1177 1178 1179 1180 1181
					Yyerror("index out of bounds")
				} else {
					// replace "abc"[1] with 'b'.
					// delayed until now because "abc"[1] is not
					// an ideal constant.
1182
					v := Mpgetfix(n.Right.Val().U.(*Mpint))
1183

1184
					Nodconst(n, n.Type, int64(n.Left.Val().U.(string)[v]))
1185 1186 1187 1188 1189
					n.Typecheck = 1
				}
			}
		}

1190
		if Isconst(n.Right, CTINT) {
1191
			if Mpcmpfixfix(n.Right.Val().U.(*Mpint), &mpzero) < 0 || Mpcmpfixfix(n.Right.Val().U.(*Mpint), Maxintval[TINT]) > 0 {
1192 1193 1194 1195 1196 1197
				Yyerror("index out of bounds")
			}
		}

	case OINDEXMAP:
		if n.Etype == 1 {
1198
			break
1199 1200 1201 1202
		}
		walkexpr(&n.Left, init)
		walkexpr(&n.Right, init)

1203 1204
		t := n.Left.Type
		p := ""
1205 1206
		if t.Type.Width <= 128 { // Check ../../runtime/hashmap.go:maxValueSize before changing.
			switch Simsimtype(t.Down) {
1207
			case TINT32, TUINT32:
1208 1209
				p = "mapaccess1_fast32"

1210
			case TINT64, TUINT64:
1211 1212 1213 1214 1215 1216 1217
				p = "mapaccess1_fast64"

			case TSTRING:
				p = "mapaccess1_faststr"
			}
		}

1218
		var key *Node
1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
		if p != "" {
			// fast versions take key by value
			key = n.Right
		} else {
			// standard version takes key by reference.
			// orderexpr made sure key is addressable.
			key = Nod(OADDR, n.Right, nil)

			p = "mapaccess1"
		}

		n = mkcall1(mapfn(p, t), Ptrto(t.Type), init, typename(t), n.Left, key)
		n = Nod(OIND, n, nil)
		n.Type = t.Type
		n.Typecheck = 1

	case ORECV:
1236
		Fatalf("walkexpr ORECV") // should see inside OAS only
1237

1238
	case OSLICE, OSLICEARR, OSLICESTR:
1239 1240
		walkexpr(&n.Left, init)
		walkexpr(&n.Right.Left, init)
1241 1242 1243 1244
		if n.Right.Left != nil && iszero(n.Right.Left) {
			// Reduce x[0:j] to x[:j].
			n.Right.Left = nil
		}
1245
		walkexpr(&n.Right.Right, init)
1246
		n = reduceSlice(n)
1247

1248
	case OSLICE3, OSLICE3ARR:
1249 1250
		walkexpr(&n.Left, init)
		walkexpr(&n.Right.Left, init)
1251 1252 1253 1254
		if n.Right.Left != nil && iszero(n.Right.Left) {
			// Reduce x[0:j:k] to x[:j:k].
			n.Right.Left = nil
		}
1255 1256
		walkexpr(&n.Right.Right.Left, init)
		walkexpr(&n.Right.Right.Right, init)
1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268

		r := n.Right.Right.Right
		if r != nil && r.Op == OCAP && samesafeexpr(n.Left, r.Left) {
			// Reduce x[i:j:cap(x)] to x[i:j].
			n.Right.Right = n.Right.Right.Left
			if n.Op == OSLICE3 {
				n.Op = OSLICE
			} else {
				n.Op = OSLICEARR
			}
			n = reduceSlice(n)
		}
1269 1270 1271 1272 1273

	case OADDR:
		walkexpr(&n.Left, init)

	case ONEW:
1274 1275
		if n.Esc == EscNone {
			if n.Type.Type.Width >= 1<<16 {
1276
				Fatalf("large ONEW with EscNone: %v", n)
1277
			}
1278
			r := temp(n.Type.Type)
1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
			r = Nod(OAS, r, nil) // zero temp
			typecheck(&r, Etop)
			*init = list(*init, r)
			r = Nod(OADDR, r.Left, nil)
			typecheck(&r, Erv)
			n = r
		} else {
			n = callnew(n.Type.Type)
		}

		// If one argument to the comparison is an empty string,
	// comparing the lengths instead will yield the same result
	// without the function call.
	case OCMPSTR:
1293
		if (Isconst(n.Left, CTSTR) && len(n.Left.Val().U.(string)) == 0) || (Isconst(n.Right, CTSTR) && len(n.Right.Val().U.(string)) == 0) {
1294 1295
			// TODO(marvin): Fix Node.EType type union.
			r := Nod(Op(n.Etype), Nod(OLEN, n.Left, nil), Nod(OLEN, n.Right, nil))
1296 1297 1298 1299
			typecheck(&r, Erv)
			walkexpr(&r, init)
			r.Type = n.Type
			n = r
1300
			break
1301 1302 1303
		}

		// s + "badgerbadgerbadger" == "badgerbadgerbadger"
1304 1305 1306
		if (Op(n.Etype) == OEQ || Op(n.Etype) == ONE) && Isconst(n.Right, CTSTR) && n.Left.Op == OADDSTR && count(n.Left.List) == 2 && Isconst(n.Left.List.Next.N, CTSTR) && strlit(n.Right) == strlit(n.Left.List.Next.N) {
			// TODO(marvin): Fix Node.EType type union.
			r := Nod(Op(n.Etype), Nod(OLEN, n.Left.List.N, nil), Nodintconst(0))
1307 1308 1309 1310
			typecheck(&r, Erv)
			walkexpr(&r, init)
			r.Type = n.Type
			n = r
1311
			break
1312 1313
		}

1314
		var r *Node
1315 1316
		// TODO(marvin): Fix Node.EType type union.
		if Op(n.Etype) == OEQ || Op(n.Etype) == ONE {
1317 1318 1319 1320 1321 1322 1323 1324 1325
			// prepare for rewrite below
			n.Left = cheapexpr(n.Left, init)

			n.Right = cheapexpr(n.Right, init)

			r = mkcall("eqstring", Types[TBOOL], init, conv(n.Left, Types[TSTRING]), conv(n.Right, Types[TSTRING]))

			// quick check of len before full compare for == or !=
			// eqstring assumes that the lengths are equal
1326 1327
			// TODO(marvin): Fix Node.EType type union.
			if Op(n.Etype) == OEQ {
1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342
				// len(left) == len(right) && eqstring(left, right)
				r = Nod(OANDAND, Nod(OEQ, Nod(OLEN, n.Left, nil), Nod(OLEN, n.Right, nil)), r)
			} else {
				// len(left) != len(right) || !eqstring(left, right)
				r = Nod(ONOT, r, nil)

				r = Nod(OOROR, Nod(ONE, Nod(OLEN, n.Left, nil), Nod(OLEN, n.Right, nil)), r)
			}

			typecheck(&r, Erv)
			walkexpr(&r, nil)
		} else {
			// sys_cmpstring(s1, s2) :: 0
			r = mkcall("cmpstring", Types[TINT], init, conv(n.Left, Types[TSTRING]), conv(n.Right, Types[TSTRING]))

1343 1344
			// TODO(marvin): Fix Node.EType type union.
			r = Nod(Op(n.Etype), r, Nodintconst(0))
1345 1346 1347 1348
		}

		typecheck(&r, Erv)
		if n.Type.Etype != TBOOL {
1349
			Fatalf("cmp %v", n.Type)
1350 1351 1352 1353 1354 1355 1356 1357
		}
		r.Type = n.Type
		n = r

	case OADDSTR:
		n = addstr(n, init)

	case OAPPEND:
1358
		// order should make sure we only see OAS(node, OAPPEND), which we handle above.
1359
		Fatalf("append outside assignment")
1360 1361

	case OCOPY:
1362
		n = copyany(n, init, instrumenting)
1363 1364 1365

		// cannot use chanfn - closechan takes any, not chan any
	case OCLOSE:
1366
		fn := syslook("closechan", 1)
1367

1368
		substArgTypes(fn, n.Left.Type)
1369 1370 1371 1372 1373 1374
		n = mkcall1(fn, nil, init, n.Left)

	case OMAKECHAN:
		n = mkcall1(chanfn("makechan", 1, n.Type), n.Type, init, typename(n.Type), conv(n.Left, Types[TINT64]))

	case OMAKEMAP:
1375
		t := n.Type
1376

1377
		fn := syslook("makemap", 1)
1378

1379 1380
		a := nodnil() // hmap buffer
		r := nodnil() // bucket buffer
1381 1382
		if n.Esc == EscNone {
			// Allocate hmap buffer on stack.
1383
			var_ := temp(hmap(t))
1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400

			a = Nod(OAS, var_, nil) // zero temp
			typecheck(&a, Etop)
			*init = list(*init, a)
			a = Nod(OADDR, var_, nil)

			// Allocate one bucket on stack.
			// Maximum key/value size is 128 bytes, larger objects
			// are stored with an indirection. So max bucket size is 2048+eps.
			var_ = temp(mapbucket(t))

			r = Nod(OAS, var_, nil) // zero temp
			typecheck(&r, Etop)
			*init = list(*init, r)
			r = Nod(OADDR, var_, nil)
		}

1401
		substArgTypes(fn, hmap(t), mapbucket(t), t.Down, t.Type)
1402 1403 1404
		n = mkcall1(fn, n.Type, init, typename(n.Type), conv(n.Left, Types[TINT64]), a, r)

	case OMAKESLICE:
1405 1406
		l := n.Left
		r := n.Right
1407 1408 1409 1410
		if r == nil {
			r = safeexpr(l, init)
			l = r
		}
1411
		t := n.Type
1412 1413
		if n.Esc == EscNone {
			if !isSmallMakeSlice(n) {
1414
				Fatalf("non-small OMAKESLICE with EscNone: %v", n)
1415
			}
1416 1417 1418
			// var arr [r]T
			// n = arr[:l]
			t = aindex(r, t.Type) // [r]T
1419 1420
			var_ := temp(t)
			a := Nod(OAS, var_, nil) // zero temp
1421 1422
			typecheck(&a, Etop)
			*init = list(*init, a)
1423
			r := Nod(OSLICE, var_, Nod(OKEY, nil, l)) // arr[:l]
1424
			r = conv(r, n.Type)                       // in case n.Type is named.
1425 1426 1427 1428 1429
			typecheck(&r, Erv)
			walkexpr(&r, init)
			n = r
		} else {
			// makeslice(t *Type, nel int64, max int64) (ary []any)
1430
			fn := syslook("makeslice", 1)
1431

1432
			substArgTypes(fn, t.Type) // any-1
1433 1434 1435 1436
			n = mkcall1(fn, n.Type, init, typename(n.Type), conv(l, Types[TINT64]), conv(r, Types[TINT64]))
		}

	case ORUNESTR:
1437
		a := nodnil()
1438
		if n.Esc == EscNone {
1439 1440
			t := aindex(Nodintconst(4), Types[TUINT8])
			var_ := temp(t)
1441 1442 1443 1444 1445 1446 1447
			a = Nod(OADDR, var_, nil)
		}

		// intstring(*[4]byte, rune)
		n = mkcall("intstring", n.Type, init, a, conv(n.Left, Types[TINT64]))

	case OARRAYBYTESTR:
1448
		a := nodnil()
1449 1450
		if n.Esc == EscNone {
			// Create temporary buffer for string on stack.
1451
			t := aindex(Nodintconst(tmpstringbufsize), Types[TUINT8])
1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464

			a = Nod(OADDR, temp(t), nil)
		}

		// slicebytetostring(*[32]byte, []byte) string;
		n = mkcall("slicebytetostring", n.Type, init, a, n.Left)

		// slicebytetostringtmp([]byte) string;
	case OARRAYBYTESTRTMP:
		n = mkcall("slicebytetostringtmp", n.Type, init, n.Left)

		// slicerunetostring(*[32]byte, []rune) string;
	case OARRAYRUNESTR:
1465
		a := nodnil()
1466 1467 1468

		if n.Esc == EscNone {
			// Create temporary buffer for string on stack.
1469
			t := aindex(Nodintconst(tmpstringbufsize), Types[TUINT8])
1470 1471 1472 1473 1474 1475 1476 1477

			a = Nod(OADDR, temp(t), nil)
		}

		n = mkcall("slicerunetostring", n.Type, init, a, n.Left)

		// stringtoslicebyte(*32[byte], string) []byte;
	case OSTRARRAYBYTE:
1478
		a := nodnil()
1479 1480 1481

		if n.Esc == EscNone {
			// Create temporary buffer for slice on stack.
1482
			t := aindex(Nodintconst(tmpstringbufsize), Types[TUINT8])
1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494

			a = Nod(OADDR, temp(t), nil)
		}

		n = mkcall("stringtoslicebyte", n.Type, init, a, conv(n.Left, Types[TSTRING]))

		// stringtoslicebytetmp(string) []byte;
	case OSTRARRAYBYTETMP:
		n = mkcall("stringtoslicebytetmp", n.Type, init, conv(n.Left, Types[TSTRING]))

		// stringtoslicerune(*[32]rune, string) []rune
	case OSTRARRAYRUNE:
1495
		a := nodnil()
1496 1497 1498

		if n.Esc == EscNone {
			// Create temporary buffer for slice on stack.
1499
			t := aindex(Nodintconst(tmpstringbufsize), Types[TINT32])
1500 1501 1502 1503 1504 1505 1506 1507 1508

			a = Nod(OADDR, temp(t), nil)
		}

		n = mkcall("stringtoslicerune", n.Type, init, a, n.Left)

		// ifaceeq(i1 any-1, i2 any-2) (ret bool);
	case OCMPIFACE:
		if !Eqtype(n.Left.Type, n.Right.Type) {
1509
			Fatalf("ifaceeq %v %v %v", Oconv(int(n.Op), 0), n.Left.Type, n.Right.Type)
1510
		}
1511
		var fn *Node
1512
		if isnilinter(n.Left.Type) {
1513 1514 1515 1516 1517 1518 1519
			fn = syslook("efaceeq", 1)
		} else {
			fn = syslook("ifaceeq", 1)
		}

		n.Right = cheapexpr(n.Right, init)
		n.Left = cheapexpr(n.Left, init)
1520
		substArgTypes(fn, n.Right.Type, n.Left.Type)
1521
		r := mkcall1(fn, n.Type, init, n.Left, n.Right)
1522 1523
		// TODO(marvin): Fix Node.EType type union.
		if Op(n.Etype) == ONE {
1524 1525 1526 1527
			r = Nod(ONOT, r, nil)
		}

		// check itable/type before full compare.
1528 1529
		// TODO(marvin): Fix Node.EType type union.
		if Op(n.Etype) == OEQ {
1530 1531 1532 1533 1534 1535 1536 1537 1538
			r = Nod(OANDAND, Nod(OEQ, Nod(OITAB, n.Left, nil), Nod(OITAB, n.Right, nil)), r)
		} else {
			r = Nod(OOROR, Nod(ONE, Nod(OITAB, n.Left, nil), Nod(OITAB, n.Right, nil)), r)
		}
		typecheck(&r, Erv)
		walkexpr(&r, init)
		r.Type = n.Type
		n = r

1539
	case OARRAYLIT, OMAPLIT, OSTRUCTLIT, OPTRLIT:
1540
		var_ := temp(n.Type)
1541 1542 1543 1544
		anylit(0, n, var_, init)
		n = var_

	case OSEND:
1545
		n1 := n.Right
1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562
		n1 = assignconv(n1, n.Left.Type.Type, "chan send")
		walkexpr(&n1, init)
		n1 = Nod(OADDR, n1, nil)
		n = mkcall1(chanfn("chansend1", 2, n.Left.Type), nil, init, typename(n.Left.Type), n.Left, n1)

	case OCLOSURE:
		n = walkclosure(n, init)

	case OCALLPART:
		n = walkpartialcall(n, init)
	}

	// Expressions that are constant at run time but not
	// considered const by the language spec are not turned into
	// constants until walk. For example, if n is y%1 == 0, the
	// walk of y%1 may have replaced it by 0.
	// Check whether n with its updated args is itself now a constant.
1563
	t := n.Type
1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580

	evconst(n)
	n.Type = t
	if n.Op == OLITERAL {
		typecheck(&n, Erv)
	}

	ullmancalc(n)

	if Debug['w'] != 0 && n != nil {
		Dump("walk", n)
	}

	lineno = lno
	*np = n
}

1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596
func reduceSlice(n *Node) *Node {
	r := n.Right.Right
	if r != nil && r.Op == OLEN && samesafeexpr(n.Left, r.Left) {
		// Reduce x[i:len(x)] to x[i:].
		n.Right.Right = nil
	}
	if (n.Op == OSLICE || n.Op == OSLICESTR) && n.Right.Left == nil && n.Right.Right == nil {
		// Reduce x[:] to x.
		if Debug_slice > 0 {
			Warn("slice: omit slice operation")
		}
		return n.Left
	}
	return n
}

1597
func ascompatee1(op Op, l *Node, r *Node, init **NodeList) *Node {
1598 1599
	// convas will turn map assigns into function calls,
	// making it impossible for reorder3 to work.
1600
	n := Nod(OAS, l, r)
1601 1602 1603 1604 1605 1606 1607 1608

	if l.Op == OINDEXMAP {
		return n
	}

	return convas(n, init)
}

1609
func ascompatee(op Op, nl *NodeList, nr *NodeList, init **NodeList) *NodeList {
1610 1611 1612
	// check assign expression list to
	// a expression list. called in
	//	expr-list = expr-list
1613 1614

	// ensure order of evaluation for function calls
1615
	for ll := nl; ll != nil; ll = ll.Next {
1616 1617
		ll.N = safeexpr(ll.N, init)
	}
1618
	for lr := nr; lr != nil; lr = lr.Next {
1619 1620 1621
		lr.N = safeexpr(lr.N, init)
	}

Russ Cox's avatar
Russ Cox committed
1622
	var nn *NodeList
1623 1624
	ll := nl
	lr := nr
1625
	for ; ll != nil && lr != nil; ll, lr = ll.Next, lr.Next {
1626 1627 1628 1629 1630 1631 1632 1633 1634
		// Do not generate 'x = x' during return. See issue 4014.
		if op == ORETURN && ll.N == lr.N {
			continue
		}
		nn = list(nn, ascompatee1(op, ll.N, lr.N, init))
	}

	// cannot happen: caller checked that lists had same length
	if ll != nil || lr != nil {
1635
		Yyerror("error in shape across %v %v %v / %d %d [%s]", Hconv(nl, obj.FmtSign), Oconv(int(op), 0), Hconv(nr, obj.FmtSign), count(nl), count(nr), Curfn.Func.Nname.Sym.Name)
1636 1637 1638 1639
	}
	return nn
}

1640 1641 1642 1643
// l is an lv and rt is the type of an rv
// return 1 if this implies a function call
// evaluating the lv or a function call
// in the conversion of the types
1644
func fncall(l *Node, rt *Type) bool {
1645
	if l.Ullman >= UINF || l.Op == OINDEXMAP {
1646
		return true
1647
	}
Russ Cox's avatar
Russ Cox committed
1648
	var r Node
1649 1650
	if needwritebarrier(l, &r) {
		return true
1651 1652
	}
	if Eqtype(l.Type, rt) {
1653
		return false
1654
	}
1655
	return true
1656 1657
}

1658
func ascompatet(op Op, nl *NodeList, nr **Type, fp int, init **NodeList) *NodeList {
1659 1660 1661 1662 1663 1664
	var l *Node
	var tmp *Node
	var a *Node
	var ll *NodeList
	var saver Iter

1665 1666 1667
	// check assign type list to
	// a expression list. called in
	//	expr-list = func()
1668
	r := Structfirst(&saver, nr)
1669

Russ Cox's avatar
Russ Cox committed
1670 1671
	var nn *NodeList
	var mm *NodeList
1672
	ucount := 0
1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685
	for ll = nl; ll != nil; ll = ll.Next {
		if r == nil {
			break
		}
		l = ll.N
		if isblank(l) {
			r = structnext(&saver)
			continue
		}

		// any lv that causes a fn call must be
		// deferred until all the return arguments
		// have been pulled from the output arguments
1686
		if fncall(l, r.Type) {
1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711
			tmp = temp(r.Type)
			typecheck(&tmp, Erv)
			a = Nod(OAS, l, tmp)
			a = convas(a, init)
			mm = list(mm, a)
			l = tmp
		}

		a = Nod(OAS, l, nodarg(r, fp))
		a = convas(a, init)
		ullmancalc(a)
		if a.Ullman >= UINF {
			Dump("ascompatet ucount", a)
			ucount++
		}

		nn = list(nn, a)
		r = structnext(&saver)
	}

	if ll != nil || r != nil {
		Yyerror("ascompatet: assignment count mismatch: %d = %d", count(nl), structcount(*nr))
	}

	if ucount != 0 {
1712
		Fatalf("ascompatet: too many function calls evaluating parameters")
1713 1714 1715 1716
	}
	return concat(nn, mm)
}

1717
// package all the arguments that match a ... T parameter into a []T.
1718
func mkdotargslice(lr0 *NodeList, nn *NodeList, l *Type, fp int, init **NodeList, ddd *Node) *NodeList {
1719
	esc := uint16(EscUnknown)
1720
	if ddd != nil {
1721
		esc = ddd.Esc
1722 1723
	}

1724
	tslice := typ(TARRAY)
1725 1726 1727
	tslice.Type = l.Type.Type
	tslice.Bound = -1

1728
	var n *Node
1729 1730 1731 1732 1733
	if count(lr0) == 0 {
		n = nodnil()
		n.Type = tslice
	} else {
		n = Nod(OCOMPLIT, nil, typenod(tslice))
Russ Cox's avatar
Russ Cox committed
1734 1735
		if ddd != nil && prealloc[ddd] != nil {
			prealloc[n] = prealloc[ddd] // temporary to use
1736 1737
		}
		n.List = lr0
1738
		n.Esc = esc
1739 1740
		typecheck(&n, Erv)
		if n.Type == nil {
1741
			Fatalf("mkdotargslice: typecheck failed")
1742 1743 1744 1745
		}
		walkexpr(&n, init)
	}

1746
	a := Nod(OAS, nodarg(l, fp), n)
1747 1748 1749 1750
	nn = list(nn, convas(a, init))
	return nn
}

1751
// helpers for shape errors
1752 1753 1754
func dumptypes(nl **Type, what string) string {
	var savel Iter

1755
	fmt_ := ""
1756
	fmt_ += "\t"
1757 1758
	first := 1
	for l := Structfirst(&savel, nl); l != nil; l = structnext(&savel) {
1759 1760 1761
		if first != 0 {
			first = 0
		} else {
1762
			fmt_ += ", "
1763
		}
1764
		fmt_ += Tconv(l, 0)
1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775
	}

	if first != 0 {
		fmt_ += fmt.Sprintf("[no arguments %s]", what)
	}
	return fmt_
}

func dumpnodetypes(l *NodeList, what string) string {
	var r *Node

1776
	fmt_ := ""
1777
	fmt_ += "\t"
1778
	first := 1
1779 1780 1781 1782 1783
	for ; l != nil; l = l.Next {
		r = l.N
		if first != 0 {
			first = 0
		} else {
1784
			fmt_ += ", "
1785
		}
1786
		fmt_ += Tconv(r.Type, 0)
1787 1788 1789 1790 1791 1792 1793 1794
	}

	if first != 0 {
		fmt_ += fmt.Sprintf("[no arguments %s]", what)
	}
	return fmt_
}

1795 1796 1797 1798
// check assign expression list to
// a type list. called in
//	return expr-list
//	func(expr-list)
1799
func ascompatte(op Op, call *Node, isddd bool, nl **Type, lr *NodeList, fp int, init **NodeList) *NodeList {
1800 1801
	var savel Iter

1802 1803
	lr0 := lr
	l := Structfirst(&savel, nl)
Russ Cox's avatar
Russ Cox committed
1804
	var r *Node
1805 1806 1807
	if lr != nil {
		r = lr.N
	}
Russ Cox's avatar
Russ Cox committed
1808
	var nn *NodeList
1809 1810

	// f(g()) where g has multiple return values
1811 1812 1813 1814
	var a *Node
	var l2 string
	var ll *Type
	var l1 string
1815
	if r != nil && lr.Next == nil && r.Type.Etype == TSTRUCT && r.Type.Funarg {
1816
		// optimization - can do block copy
1817
		if eqtypenoname(r.Type, *nl) {
1818
			a := nodarg(*nl, fp)
1819 1820 1821 1822 1823 1824 1825 1826
			r = Nod(OCONVNOP, r, nil)
			r.Type = a.Type
			nn = list1(convas(Nod(OAS, a, r), init))
			goto ret
		}

		// conversions involved.
		// copy into temporaries.
Russ Cox's avatar
Russ Cox committed
1827
		var alist *NodeList
1828

1829
		for l := Structfirst(&savel, &r.Type); l != nil; l = structnext(&savel) {
1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845
			a = temp(l.Type)
			alist = list(alist, a)
		}

		a = Nod(OAS2, nil, nil)
		a.List = alist
		a.Rlist = lr
		typecheck(&a, Etop)
		walkstmt(&a)
		*init = list(*init, a)
		lr = alist
		r = lr.N
		l = Structfirst(&savel, nl)
	}

loop:
1846
	if l != nil && l.Isddd {
1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857
		// the ddd parameter must be last
		ll = structnext(&savel)

		if ll != nil {
			Yyerror("... must be last argument")
		}

		// special case --
		// only if we are assigning a single ddd
		// argument to a ddd parameter then it is
		// passed thru unencapsulated
1858
		if r != nil && lr.Next == nil && isddd && Eqtype(l.Type, r.Type) {
1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911
			a = Nod(OAS, nodarg(l, fp), r)
			a = convas(a, init)
			nn = list(nn, a)
			goto ret
		}

		// normal case -- make a slice of all
		// remaining arguments and pass it to
		// the ddd parameter.
		nn = mkdotargslice(lr, nn, l, fp, init, call.Right)

		goto ret
	}

	if l == nil || r == nil {
		if l != nil || r != nil {
			l1 = dumptypes(nl, "expected")
			l2 = dumpnodetypes(lr0, "given")
			if l != nil {
				Yyerror("not enough arguments to %v\n%s\n%s", Oconv(int(op), 0), l1, l2)
			} else {
				Yyerror("too many arguments to %v\n%s\n%s", Oconv(int(op), 0), l1, l2)
			}
		}

		goto ret
	}

	a = Nod(OAS, nodarg(l, fp), r)
	a = convas(a, init)
	nn = list(nn, a)

	l = structnext(&savel)
	r = nil
	lr = lr.Next
	if lr != nil {
		r = lr.N
	}
	goto loop

ret:
	for lr = nn; lr != nil; lr = lr.Next {
		lr.N.Typecheck = 1
	}
	return nn
}

// generate code for print
func walkprint(nn *Node, init **NodeList) *Node {
	var r *Node
	var n *Node
	var on *Node
	var t *Type
1912
	var et EType
1913

1914
	op := nn.Op
1915
	all := nn.List
Russ Cox's avatar
Russ Cox committed
1916
	var calls *NodeList
1917
	notfirst := false
1918 1919 1920 1921 1922 1923

	// Hoist all the argument evaluation up before the lock.
	walkexprlistcheap(all, init)

	calls = list(calls, mkcall("printlock", nil, init))

1924
	for l := all; l != nil; l = l.Next {
1925
		if notfirst {
1926 1927 1928
			calls = list(calls, mkcall("printsp", nil, init))
		}

1929
		notfirst = op == OPRINTN
1930 1931 1932

		n = l.N
		if n.Op == OLITERAL {
1933
			switch n.Val().Ctype() {
1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954
			case CTRUNE:
				defaultlit(&n, runetype)

			case CTINT:
				defaultlit(&n, Types[TINT64])

			case CTFLT:
				defaultlit(&n, Types[TFLOAT64])
			}
		}

		if n.Op != OLITERAL && n.Type != nil && n.Type.Etype == TIDEAL {
			defaultlit(&n, Types[TINT64])
		}
		defaultlit(&n, nil)
		l.N = n
		if n.Type == nil || n.Type.Etype == TFORW {
			continue
		}

		t = n.Type
1955
		et = n.Type.Etype
1956 1957
		if Isinter(n.Type) {
			if isnilinter(n.Type) {
1958 1959 1960 1961
				on = syslook("printeface", 1)
			} else {
				on = syslook("printiface", 1)
			}
1962
			substArgTypes(on, n.Type) // any-1
1963
		} else if Isptr[et] || et == TCHAN || et == TMAP || et == TFUNC || et == TUNSAFEPTR {
1964
			on = syslook("printpointer", 1)
1965
			substArgTypes(on, n.Type) // any-1
1966
		} else if Isslice(n.Type) {
1967
			on = syslook("printslice", 1)
1968
			substArgTypes(on, n.Type) // any-1
1969
		} else if Isint[et] {
1970 1971 1972 1973 1974 1975 1976 1977 1978
			if et == TUINT64 {
				if (t.Sym.Pkg == Runtimepkg || compiling_runtime != 0) && t.Sym.Name == "hex" {
					on = syslook("printhex", 0)
				} else {
					on = syslook("printuint", 0)
				}
			} else {
				on = syslook("printint", 0)
			}
1979
		} else if Isfloat[et] {
1980
			on = syslook("printfloat", 0)
1981
		} else if Iscomplex[et] {
1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027
			on = syslook("printcomplex", 0)
		} else if et == TBOOL {
			on = syslook("printbool", 0)
		} else if et == TSTRING {
			on = syslook("printstring", 0)
		} else {
			badtype(OPRINT, n.Type, nil)
			continue
		}

		t = *getinarg(on.Type)
		if t != nil {
			t = t.Type
		}
		if t != nil {
			t = t.Type
		}

		if !Eqtype(t, n.Type) {
			n = Nod(OCONV, n, nil)
			n.Type = t
		}

		r = Nod(OCALL, on, nil)
		r.List = list1(n)
		calls = list(calls, r)
	}

	if op == OPRINTN {
		calls = list(calls, mkcall("printnl", nil, nil))
	}

	calls = list(calls, mkcall("printunlock", nil, init))

	typechecklist(calls, Etop)
	walkexprlist(calls, init)

	r = Nod(OEMPTY, nil, nil)
	typecheck(&r, Etop)
	walkexpr(&r, init)
	r.Ninit = calls
	return r
}

func callnew(t *Type) *Node {
	dowidth(t)
2028
	fn := syslook("newobject", 1)
2029
	substArgTypes(fn, t)
2030 2031 2032
	return mkcall1(fn, Ptrto(t), nil, typename(t))
}

2033 2034 2035 2036 2037
func iscallret(n *Node) bool {
	n = outervalue(n)
	return n.Op == OINDREG && n.Reg == int16(Thearch.REGSP)
}

2038
func isstack(n *Node) bool {
2039 2040 2041 2042 2043
	n = outervalue(n)

	// If n is *autotmp and autotmp = &foo, replace n with foo.
	// We introduce such temps when initializing struct literals.
	if n.Op == OIND && n.Left.Op == ONAME && strings.HasPrefix(n.Left.Sym.Name, "autotmp_") {
2044
		defn := n.Left.Name.Defn
2045 2046 2047 2048 2049 2050 2051
		if defn != nil && defn.Op == OAS && defn.Right.Op == OADDR {
			n = defn.Right.Left
		}
	}

	switch n.Op {
	case OINDREG:
2052
		return n.Reg == int16(Thearch.REGSP)
2053 2054 2055

	case ONAME:
		switch n.Class {
2056
		case PAUTO, PPARAM, PPARAMOUT:
2057
			return true
2058 2059 2060
		}
	}

2061
	return false
2062 2063
}

2064
func isglobal(n *Node) bool {
2065 2066 2067 2068 2069 2070
	n = outervalue(n)

	switch n.Op {
	case ONAME:
		switch n.Class {
		case PEXTERN:
2071
			return true
2072 2073 2074
		}
	}

2075
	return false
2076 2077 2078
}

// Do we need a write barrier for the assignment l = r?
2079 2080 2081
func needwritebarrier(l *Node, r *Node) bool {
	if use_writebarrier == 0 {
		return false
2082 2083 2084
	}

	if l == nil || isblank(l) {
2085
		return false
2086 2087 2088 2089 2090 2091
	}

	// No write barrier for write of non-pointers.
	dowidth(l.Type)

	if !haspointers(l.Type) {
2092
		return false
2093 2094 2095
	}

	// No write barrier for write to stack.
2096 2097
	if isstack(l) {
		return false
2098 2099
	}

2100 2101
	// No write barrier for implicit zeroing.
	if r == nil {
2102
		return false
2103 2104
	}

2105 2106 2107 2108 2109 2110 2111 2112 2113
	// Ignore no-op conversions when making decision.
	// Ensures that xp = unsafe.Pointer(&x) is treated
	// the same as xp = &x.
	for r.Op == OCONVNOP {
		r = r.Left
	}

	// No write barrier for zeroing or initialization to constant.
	if iszero(r) || r.Op == OLITERAL {
2114
		return false
2115 2116 2117 2118
	}

	// No write barrier for storing static (read-only) data.
	if r.Op == ONAME && strings.HasPrefix(r.Sym.Name, "statictmp_") {
2119
		return false
2120 2121 2122 2123
	}

	// No write barrier for storing address of stack values,
	// which are guaranteed only to be written to the stack.
2124 2125
	if r.Op == OADDR && isstack(r.Left) {
		return false
2126 2127 2128 2129
	}

	// No write barrier for storing address of global, which
	// is live no matter what.
2130 2131
	if r.Op == OADDR && isglobal(r.Left) {
		return false
2132 2133 2134
	}

	// Otherwise, be conservative and use write barrier.
2135
	return true
2136 2137 2138 2139 2140
}

// TODO(rsc): Perhaps componentgen should run before this.

func applywritebarrier(n *Node, init **NodeList) *Node {
2141
	if n.Left != nil && n.Right != nil && needwritebarrier(n.Left, n.Right) {
2142 2143
		if Debug_wb > 1 {
			Warnl(int(n.Lineno), "marking %v for barrier", Nconv(n.Left, 0))
2144
		}
2145 2146
		n.Op = OASWB
		return n
2147 2148 2149 2150 2151 2152
	}
	return n
}

func convas(n *Node, init **NodeList) *Node {
	if n.Op != OAS {
2153
		Fatalf("convas: not OAS %v", Oconv(int(n.Op), 0))
2154 2155 2156 2157
	}

	n.Typecheck = 1

2158 2159
	var lt *Type
	var rt *Type
2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175
	if n.Left == nil || n.Right == nil {
		goto out
	}

	lt = n.Left.Type
	rt = n.Right.Type
	if lt == nil || rt == nil {
		goto out
	}

	if isblank(n.Left) {
		defaultlit(&n.Right, nil)
		goto out
	}

	if n.Left.Op == OINDEXMAP {
2176 2177 2178
		map_ := n.Left.Left
		key := n.Left.Right
		val := n.Right
2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200
		walkexpr(&map_, init)
		walkexpr(&key, init)
		walkexpr(&val, init)

		// orderexpr made sure key and val are addressable.
		key = Nod(OADDR, key, nil)

		val = Nod(OADDR, val, nil)
		n = mkcall1(mapfn("mapassign1", map_.Type), nil, init, typename(map_.Type), map_, key, val)
		goto out
	}

	if !Eqtype(lt, rt) {
		n.Right = assignconv(n.Right, lt, "assignment")
		walkexpr(&n.Right, init)
	}

out:
	ullmancalc(n)
	return n
}

2201 2202 2203 2204 2205 2206
// from ascompat[te]
// evaluating actual function arguments.
//	f(a,b)
// if there is exactly one function expr,
// then it is done first. otherwise must
// make temp variables
2207 2208 2209
func reorder1(all *NodeList) *NodeList {
	var n *Node

2210 2211
	c := 0 // function calls
	t := 0 // total parameters
2212

2213
	for l := all; l != nil; l = l.Next {
2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225
		n = l.N
		t++
		ullmancalc(n)
		if n.Ullman >= UINF {
			c++
		}
	}

	if c == 0 || t == 1 {
		return all
	}

Russ Cox's avatar
Russ Cox committed
2226 2227 2228
	var g *NodeList // fncalls assigned to tempnames
	var f *Node     // last fncall assigned to stack
	var r *NodeList // non fncalls and tempnames assigned to stack
2229 2230 2231
	d := 0
	var a *Node
	for l := all; l != nil; l = l.Next {
2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262
		n = l.N
		if n.Ullman < UINF {
			r = list(r, n)
			continue
		}

		d++
		if d == c {
			f = n
			continue
		}

		// make assignment of fncall to tempname
		a = temp(n.Right.Type)

		a = Nod(OAS, a, n.Right)
		g = list(g, a)

		// put normal arg assignment on list
		// with fncall replaced by tempname
		n.Right = a.Left

		r = list(r, n)
	}

	if f != nil {
		g = list(g, f)
	}
	return concat(g, r)
}

2263 2264 2265 2266 2267 2268
// from ascompat[ee]
//	a,b = c,d
// simultaneous assignment. there cannot
// be later use of an earlier lvalue.
//
// function calls have been removed.
2269 2270 2271 2272 2273 2274
func reorder3(all *NodeList) *NodeList {
	var l *Node

	// If a needed expression may be affected by an
	// earlier assignment, make an early copy of that
	// expression and use the copy instead.
Russ Cox's avatar
Russ Cox committed
2275
	var early *NodeList
2276

Russ Cox's avatar
Russ Cox committed
2277
	var mapinit *NodeList
2278
	for list := all; list != nil; list = list.Next {
2279 2280 2281 2282 2283 2284 2285 2286 2287 2288
		l = list.N.Left

		// Save subexpressions needed on left side.
		// Drill through non-dereferences.
		for {
			if l.Op == ODOT || l.Op == OPAREN {
				l = l.Left
				continue
			}

2289
			if l.Op == OINDEX && Isfixedarray(l.Left.Type) {
2290 2291 2292 2293 2294 2295 2296 2297 2298 2299
				reorder3save(&l.Right, all, list, &early)
				l = l.Left
				continue
			}

			break
		}

		switch l.Op {
		default:
2300
			Fatalf("reorder3 unexpected lvalue %v", Oconv(int(l.Op), obj.FmtSharp))
2301 2302 2303 2304

		case ONAME:
			break

2305
		case OINDEX, OINDEXMAP:
2306 2307 2308 2309 2310 2311
			reorder3save(&l.Left, all, list, &early)
			reorder3save(&l.Right, all, list, &early)
			if l.Op == OINDEXMAP {
				list.N = convas(list.N, &mapinit)
			}

2312
		case OIND, ODOTPTR:
2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323
			reorder3save(&l.Left, all, list, &early)
		}

		// Save expression on right side.
		reorder3save(&list.N.Right, all, list, &early)
	}

	early = concat(mapinit, early)
	return concat(early, all)
}

2324 2325 2326 2327
// if the evaluation of *np would be affected by the
// assignments in all up to but not including stop,
// copy into a temporary during *early and
// replace *np with that temp.
2328
func reorder3save(np **Node, all *NodeList, stop *NodeList, early **NodeList) {
2329
	n := *np
2330
	if !aliased(n, all, stop) {
2331 2332 2333
		return
	}

2334
	q := temp(n.Type)
2335 2336 2337 2338 2339 2340
	q = Nod(OAS, q, n)
	typecheck(&q, Etop)
	*early = list(*early, q)
	*np = q.Left
}

2341 2342
// what's the outer value that a write to n affects?
// outer value means containing struct or array.
2343 2344 2345
func outervalue(n *Node) *Node {
	for {
		if n.Op == OXDOT {
2346
			Fatalf("OXDOT in walk")
2347 2348 2349 2350 2351 2352
		}
		if n.Op == ODOT || n.Op == OPAREN || n.Op == OCONVNOP {
			n = n.Left
			continue
		}

2353
		if n.Op == OINDEX && Isfixedarray(n.Left.Type) {
2354 2355 2356 2357 2358 2359 2360 2361 2362 2363
			n = n.Left
			continue
		}

		break
	}

	return n
}

2364 2365
// Is it possible that the computation of n might be
// affected by writes in as up to but not including stop?
2366
func aliased(n *Node, all *NodeList, stop *NodeList) bool {
2367
	if n == nil {
2368
		return false
2369 2370 2371 2372 2373 2374 2375
	}

	// Look for obvious aliasing: a variable being assigned
	// during the all list and appearing in n.
	// Also record whether there are any writes to main memory.
	// Also record whether there are any writes to variables
	// whose addresses have been taken.
2376
	memwrite := 0
2377

2378 2379 2380
	varwrite := 0
	var a *Node
	for l := all; l != stop; l = l.Next {
2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391
		a = outervalue(l.N.Left)
		if a.Op != ONAME {
			memwrite = 1
			continue
		}

		switch n.Class {
		default:
			varwrite = 1
			continue

2392
		case PAUTO, PPARAM, PPARAMOUT:
2393
			if n.Addrtaken {
2394 2395 2396 2397
				varwrite = 1
				continue
			}

2398
			if vmatch2(a, n) {
2399
				// Direct hit.
2400
				return true
2401 2402 2403 2404 2405 2406 2407 2408 2409
			}
		}
	}

	// The variables being written do not appear in n.
	// However, n might refer to computed addresses
	// that are being written.

	// If no computed addresses are affected by the writes, no aliasing.
2410 2411
	if memwrite == 0 && varwrite == 0 {
		return false
2412 2413 2414 2415 2416
	}

	// If n does not refer to computed addresses
	// (that is, if n only refers to variables whose addresses
	// have not been taken), no aliasing.
2417 2418
	if varexpr(n) {
		return false
2419 2420 2421 2422
	}

	// Otherwise, both the writes and n refer to computed memory addresses.
	// Assume that they might conflict.
2423
	return true
2424 2425
}

2426 2427 2428
// does the evaluation of n only refer to variables
// whose addresses have not been taken?
// (and no other memory)
2429
func varexpr(n *Node) bool {
2430
	if n == nil {
2431
		return true
2432 2433 2434 2435
	}

	switch n.Op {
	case OLITERAL:
2436
		return true
2437 2438 2439

	case ONAME:
		switch n.Class {
2440
		case PAUTO, PPARAM, PPARAMOUT:
2441
			if !n.Addrtaken {
2442
				return true
2443 2444 2445
			}
		}

2446
		return false
2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469

	case OADD,
		OSUB,
		OOR,
		OXOR,
		OMUL,
		ODIV,
		OMOD,
		OLSH,
		ORSH,
		OAND,
		OANDNOT,
		OPLUS,
		OMINUS,
		OCOM,
		OPAREN,
		OANDAND,
		OOROR,
		ODOT, // but not ODOTPTR
		OCONV,
		OCONVNOP,
		OCONVIFACE,
		ODOTTYPE:
2470
		return varexpr(n.Left) && varexpr(n.Right)
2471 2472 2473
	}

	// Be conservative.
2474
	return false
2475 2476
}

2477
// is the name l mentioned in r?
2478
func vmatch2(l *Node, r *Node) bool {
2479
	if r == nil {
2480
		return false
2481 2482 2483 2484
	}
	switch r.Op {
	// match each right given left
	case ONAME:
2485
		return l == r
2486 2487

	case OLITERAL:
2488
		return false
2489 2490
	}

2491 2492
	if vmatch2(l, r.Left) {
		return true
2493
	}
2494 2495
	if vmatch2(l, r.Right) {
		return true
2496
	}
2497
	for ll := r.List; ll != nil; ll = ll.Next {
2498 2499
		if vmatch2(l, ll.N) {
			return true
2500 2501
		}
	}
2502
	return false
2503 2504
}

2505 2506
// is any name mentioned in l also mentioned in r?
// called by sinit.go
2507
func vmatch1(l *Node, r *Node) bool {
2508
	// isolate all left sides
2509
	if l == nil || r == nil {
2510
		return false
2511 2512 2513 2514
	}
	switch l.Op {
	case ONAME:
		switch l.Class {
2515
		case PPARAM, PPARAMREF, PAUTO:
2516 2517 2518 2519 2520 2521
			break

			// assignment to non-stack variable
		// must be delayed if right has function calls.
		default:
			if r.Ullman >= UINF {
2522
				return true
2523 2524 2525 2526 2527 2528
			}
		}

		return vmatch2(l, r)

	case OLITERAL:
2529
		return false
2530 2531
	}

2532 2533
	if vmatch1(l.Left, r) {
		return true
2534
	}
2535 2536
	if vmatch1(l.Right, r) {
		return true
2537
	}
2538
	for ll := l.List; ll != nil; ll = ll.Next {
2539 2540
		if vmatch1(ll.N, r) {
			return true
2541 2542
		}
	}
2543
	return false
2544 2545
}

2546 2547 2548
// walk through argin parameters.
// generate and return code to allocate
// copies of escaped parameters to the heap.
2549 2550 2551 2552 2553
func paramstoheap(argin **Type, out int) *NodeList {
	var savet Iter
	var v *Node
	var as *Node

Russ Cox's avatar
Russ Cox committed
2554
	var nn *NodeList
2555
	for t := Structfirst(&savet, argin); t != nil; t = structnext(&savet) {
2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569
		v = t.Nname
		if v != nil && v.Sym != nil && v.Sym.Name[0] == '~' && v.Sym.Name[1] == 'r' { // unnamed result
			v = nil
		}

		// For precise stacks, the garbage collector assumes results
		// are always live, so zero them always.
		if out != 0 {
			// Defer might stop a panic and show the
			// return values as they exist at the time of panic.
			// Make sure to zero them on entry to the function.
			nn = list(nn, Nod(OAS, nodarg(t, 1), nil))
		}

2570
		if v == nil || v.Class&PHEAP == 0 {
2571 2572 2573 2574 2575
			continue
		}

		// generate allocation & copying code
		if compiling_runtime != 0 {
2576
			Yyerror("%v escapes to heap, not allowed in runtime.", v)
2577
		}
Russ Cox's avatar
Russ Cox committed
2578 2579
		if prealloc[v] == nil {
			prealloc[v] = callnew(v.Type)
2580
		}
Russ Cox's avatar
Russ Cox committed
2581
		nn = list(nn, Nod(OAS, v.Name.Heapaddr, prealloc[v]))
2582
		if v.Class&^PHEAP != PPARAMOUT {
2583
			as = Nod(OAS, v, v.Name.Param.Stackparam)
2584
			v.Name.Param.Stackparam.Typecheck = 1
2585 2586 2587 2588 2589 2590 2591 2592 2593
			typecheck(&as, Etop)
			as = applywritebarrier(as, &nn)
			nn = list(nn, as)
		}
	}

	return nn
}

2594
// walk through argout parameters copying back to stack
2595 2596 2597 2598
func returnsfromheap(argin **Type) *NodeList {
	var savet Iter
	var v *Node

Russ Cox's avatar
Russ Cox committed
2599
	var nn *NodeList
2600
	for t := Structfirst(&savet, argin); t != nil; t = structnext(&savet) {
2601 2602 2603 2604
		v = t.Nname
		if v == nil || v.Class != PHEAP|PPARAMOUT {
			continue
		}
2605
		nn = list(nn, Nod(OAS, v.Name.Param.Stackparam, v))
2606 2607 2608 2609 2610
	}

	return nn
}

2611 2612 2613
// take care of migrating any function in/out args
// between the stack and the heap.  adds code to
// curfn's before and after lists.
2614
func heapmoves() {
2615
	lno := lineno
2616
	lineno = Curfn.Lineno
2617
	nn := paramstoheap(getthis(Curfn.Type), 0)
2618 2619
	nn = concat(nn, paramstoheap(getinarg(Curfn.Type), 0))
	nn = concat(nn, paramstoheap(Getoutarg(Curfn.Type), 1))
2620 2621 2622
	Curfn.Func.Enter = concat(Curfn.Func.Enter, nn)
	lineno = Curfn.Func.Endlineno
	Curfn.Func.Exit = returnsfromheap(Getoutarg(Curfn.Type))
2623 2624 2625 2626 2627
	lineno = lno
}

func vmkcall(fn *Node, t *Type, init **NodeList, va []*Node) *Node {
	if fn.Type == nil || fn.Type.Etype != TFUNC {
2628
		Fatalf("mkcall %v %v", fn, fn.Type)
2629 2630
	}

Russ Cox's avatar
Russ Cox committed
2631
	var args *NodeList
2632 2633
	n := fn.Type.Intuple
	for i := 0; i < n; i++ {
2634 2635 2636
		args = list(args, va[i])
	}

2637
	r := Nod(OCALL, fn, nil)
2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668
	r.List = args
	if fn.Type.Outtuple > 0 {
		typecheck(&r, Erv|Efnstruct)
	} else {
		typecheck(&r, Etop)
	}
	walkexpr(&r, init)
	r.Type = t
	return r
}

func mkcall(name string, t *Type, init **NodeList, args ...*Node) *Node {
	return vmkcall(syslook(name, 0), t, init, args)
}

func mkcall1(fn *Node, t *Type, init **NodeList, args ...*Node) *Node {
	return vmkcall(fn, t, init, args)
}

func conv(n *Node, t *Type) *Node {
	if Eqtype(n.Type, t) {
		return n
	}
	n = Nod(OCONV, n, nil)
	n.Type = t
	typecheck(&n, Erv)
	return n
}

func chanfn(name string, n int, t *Type) *Node {
	if t.Etype != TCHAN {
2669
		Fatalf("chanfn %v", t)
2670
	}
2671
	fn := syslook(name, 1)
2672 2673
	switch n {
	default:
2674
		Fatalf("chanfn %d", n)
2675 2676 2677 2678
	case 1:
		substArgTypes(fn, t.Type)
	case 2:
		substArgTypes(fn, t.Type, t.Type)
2679 2680 2681 2682 2683 2684
	}
	return fn
}

func mapfn(name string, t *Type) *Node {
	if t.Etype != TMAP {
2685
		Fatalf("mapfn %v", t)
2686
	}
2687
	fn := syslook(name, 1)
2688
	substArgTypes(fn, t.Down, t.Type, t.Down, t.Type)
2689 2690 2691 2692 2693
	return fn
}

func mapfndel(name string, t *Type) *Node {
	if t.Etype != TMAP {
2694
		Fatalf("mapfn %v", t)
2695
	}
2696
	fn := syslook(name, 1)
2697
	substArgTypes(fn, t.Down, t.Type, t.Down)
2698 2699 2700 2701
	return fn
}

func writebarrierfn(name string, l *Type, r *Type) *Node {
2702
	fn := syslook(name, 1)
2703
	substArgTypes(fn, l, r)
2704 2705 2706 2707 2708
	return fn
}

func addstr(n *Node, init **NodeList) *Node {
	// orderexpr rewrote OADDSTR to have a list of strings.
2709
	c := count(n.List)
2710 2711 2712 2713 2714

	if c < 2 {
		Yyerror("addstr count %d too small", c)
	}

2715
	buf := nodnil()
2716
	if n.Esc == EscNone {
2717 2718
		sz := int64(0)
		for l := n.List; l != nil; l = l.Next {
2719
			if n.Op == OLITERAL {
2720
				sz += int64(len(n.Val().U.(string)))
2721 2722 2723 2724 2725 2726
			}
		}

		// Don't allocate the buffer if the result won't fit.
		if sz < tmpstringbufsize {
			// Create temporary buffer for result string on stack.
2727
			t := aindex(Nodintconst(tmpstringbufsize), Types[TUINT8])
2728 2729 2730 2731 2732 2733

			buf = Nod(OADDR, temp(t), nil)
		}
	}

	// build list of string arguments
2734
	args := list1(buf)
2735

2736
	for l := n.List; l != nil; l = l.Next {
2737 2738 2739
		args = list(args, conv(l.N, Types[TSTRING]))
	}

2740
	var fn string
2741 2742 2743
	if c <= 5 {
		// small numbers of strings use direct runtime helpers.
		// note: orderexpr knows this cutoff too.
2744
		fn = fmt.Sprintf("concatstring%d", c)
2745 2746
	} else {
		// large numbers of strings are passed to the runtime as a slice.
2747
		fn = "concatstrings"
2748

2749
		t := typ(TARRAY)
2750 2751
		t.Type = Types[TSTRING]
		t.Bound = -1
2752
		slice := Nod(OCOMPLIT, nil, typenod(t))
Russ Cox's avatar
Russ Cox committed
2753 2754 2755
		if prealloc[n] != nil {
			prealloc[slice] = prealloc[n]
		}
2756 2757 2758 2759 2760 2761
		slice.List = args.Next // skip buf arg
		args = list1(buf)
		args = list(args, slice)
		slice.Esc = EscNone
	}

2762
	cat := syslook(fn, 1)
2763
	r := Nod(OCALL, cat, nil)
2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775
	r.List = args
	typecheck(&r, Erv)
	walkexpr(&r, init)
	r.Type = n.Type

	return r
}

// expand append(l1, l2...) to
//   init {
//     s := l1
//     if n := len(l1) + len(l2) - cap(s); n > 0 {
2776
//       s = growslice_n(s, n)
2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789
//     }
//     s = s[:len(l1)+len(l2)]
//     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
//   }
//   s
//
// l2 is allowed to be a string.
func appendslice(n *Node, init **NodeList) *Node {
	walkexprlistsafe(n.List, init)

	// walkexprlistsafe will leave OINDEX (s[n]) alone if both s
	// and n are name or literal, but those may index the slice we're
	// modifying here.  Fix explicitly.
2790
	for l := n.List; l != nil; l = l.Next {
2791 2792 2793
		l.N = cheapexpr(l.N, init)
	}

2794 2795
	l1 := n.List.N
	l2 := n.List.Next.N
2796

2797
	s := temp(l1.Type) // var s []T
Russ Cox's avatar
Russ Cox committed
2798
	var l *NodeList
2799 2800
	l = list(l, Nod(OAS, s, l1)) // s = l1

2801
	nt := temp(Types[TINT])
2802

2803
	nif := Nod(OIF, nil, nil)
2804 2805 2806 2807

	// n := len(s) + len(l2) - cap(s)
	nif.Ninit = list1(Nod(OAS, nt, Nod(OSUB, Nod(OADD, Nod(OLEN, s, nil), Nod(OLEN, l2, nil)), Nod(OCAP, s, nil))))

2808
	nif.Left = Nod(OGT, nt, Nodintconst(0))
2809

2810 2811
	// instantiate growslice_n(Type*, []any, int) []any
	fn := syslook("growslice_n", 1) //   growslice_n(<type>, old []T, n int64) (ret []T)
2812
	substArgTypes(fn, s.Type.Type, s.Type.Type)
2813

2814
	// s = growslice_n(T, s, n)
2815
	nif.Nbody = list1(Nod(OAS, s, mkcall1(fn, s.Type, &nif.Ninit, typename(s.Type), s, nt)))
2816 2817 2818 2819 2820

	l = list(l, nif)

	if haspointers(l1.Type.Type) {
		// copy(s[len(l1):len(l1)+len(l2)], l2)
2821
		nptr1 := Nod(OSLICE, s, Nod(OKEY, Nod(OLEN, l1, nil), Nod(OADD, Nod(OLEN, l1, nil), Nod(OLEN, l2, nil))))
2822 2823

		nptr1.Etype = 1
2824 2825
		nptr2 := l2
		fn := syslook("typedslicecopy", 1)
2826
		substArgTypes(fn, l1.Type, l2.Type)
2827
		nt := mkcall1(fn, Types[TINT], &l, typename(l1.Type.Type), nptr1, nptr2)
2828
		l = list(l, nt)
2829
	} else if instrumenting {
2830 2831
		// rely on runtime to instrument copy.
		// copy(s[len(l1):len(l1)+len(l2)], l2)
2832
		nptr1 := Nod(OSLICE, s, Nod(OKEY, Nod(OLEN, l1, nil), Nod(OADD, Nod(OLEN, l1, nil), Nod(OLEN, l2, nil))))
2833 2834

		nptr1.Etype = 1
2835 2836
		nptr2 := l2
		var fn *Node
2837 2838 2839 2840 2841
		if l2.Type.Etype == TSTRING {
			fn = syslook("slicestringcopy", 1)
		} else {
			fn = syslook("slicecopy", 1)
		}
2842
		substArgTypes(fn, l1.Type, l2.Type)
2843
		nt := mkcall1(fn, Types[TINT], &l, nptr1, nptr2, Nodintconst(s.Type.Type.Width))
2844 2845 2846
		l = list(l, nt)
	} else {
		// memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
2847
		nptr1 := Nod(OINDEX, s, Nod(OLEN, l1, nil))
2848

2849
		nptr1.Bounded = true
2850 2851
		nptr1 = Nod(OADDR, nptr1, nil)

2852
		nptr2 := Nod(OSPTR, l2, nil)
2853

2854
		fn := syslook("memmove", 1)
2855
		substArgTypes(fn, s.Type.Type, s.Type.Type)
2856

2857
		nwid := cheapexpr(conv(Nod(OLEN, l2, nil), Types[TUINTPTR]), &l)
2858 2859

		nwid = Nod(OMUL, nwid, Nodintconst(s.Type.Type.Width))
2860
		nt := mkcall1(fn, nil, &l, nptr1, nptr2, nwid)
2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876
		l = list(l, nt)
	}

	// s = s[:len(l1)+len(l2)]
	nt = Nod(OADD, Nod(OLEN, l1, nil), Nod(OLEN, l2, nil))

	nt = Nod(OSLICE, s, Nod(OKEY, nil, nt))
	nt.Etype = 1
	l = list(l, Nod(OAS, s, nt))

	typechecklist(l, Etop)
	walkstmtlist(l)
	*init = concat(*init, l)
	return s
}

2877 2878 2879 2880 2881 2882 2883
// Rewrite append(src, x, y, z) so that any side effects in
// x, y, z (including runtime panics) are evaluated in
// initialization statements before the append.
// For normal code generation, stop there and leave the
// rest to cgen_append.
//
// For race detector, expand append(src, a [, b]* ) to
2884 2885 2886 2887 2888
//
//   init {
//     s := src
//     const argc = len(args) - 1
//     if cap(s) - len(s) < argc {
2889
//	    s = growslice(s, len(s)+argc)
2890 2891 2892 2893 2894 2895 2896 2897
//     }
//     n := len(s)
//     s = s[:n+argc]
//     s[n] = a
//     s[n+1] = b
//     ...
//   }
//   s
2898 2899 2900 2901 2902 2903 2904
func walkappend(n *Node, init **NodeList, dst *Node) *Node {
	if !samesafeexpr(dst, n.List.N) {
		l := n.List
		l.N = safeexpr(l.N, init)
		walkexpr(&l.N, init)
	}
	walkexprlistsafe(n.List.Next, init)
2905 2906 2907 2908

	// walkexprlistsafe will leave OINDEX (s[n]) alone if both s
	// and n are name or literal, but those may index the slice we're
	// modifying here.  Fix explicitly.
2909 2910 2911 2912
	// Using cheapexpr also makes sure that the evaluation
	// of all arguments (and especially any panics) happen
	// before we begin to modify the slice in a visible way.
	for l := n.List.Next; l != nil; l = l.Next {
2913 2914 2915
		l.N = cheapexpr(l.N, init)
	}

2916
	nsrc := n.List.N
2917 2918

	// Resolve slice type of multi-valued return.
2919
	if Istype(nsrc.Type, TSTRUCT) {
2920 2921
		nsrc.Type = nsrc.Type.Type.Type
	}
2922
	argc := count(n.List) - 1
2923 2924 2925 2926
	if argc < 1 {
		return nsrc
	}

2927
	// General case, with no function calls left as arguments.
2928
	// Leave for gen, except that instrumentation requires old form.
2929
	if !instrumenting {
2930 2931 2932
		return n
	}

Russ Cox's avatar
Russ Cox committed
2933
	var l *NodeList
2934

2935
	ns := temp(nsrc.Type)
2936 2937
	l = list(l, Nod(OAS, ns, nsrc)) // s = src

2938 2939
	na := Nodintconst(int64(argc)) // const argc
	nx := Nod(OIF, nil, nil)       // if cap(s) - len(s) < argc
2940
	nx.Left = Nod(OLT, Nod(OSUB, Nod(OCAP, ns, nil), Nod(OLEN, ns, nil)), na)
2941

2942
	fn := syslook("growslice", 1) //   growslice(<type>, old []T, mincap int) (ret []T)
2943
	substArgTypes(fn, ns.Type.Type, ns.Type.Type)
2944

2945
	nx.Nbody = list1(Nod(OAS, ns, mkcall1(fn, ns.Type, &nx.Ninit, typename(ns.Type), ns, Nod(OADD, Nod(OLEN, ns, nil), na))))
2946 2947 2948

	l = list(l, nx)

2949
	nn := temp(Types[TINT])
2950 2951 2952 2953 2954 2955
	l = list(l, Nod(OAS, nn, Nod(OLEN, ns, nil))) // n = len(s)

	nx = Nod(OSLICE, ns, Nod(OKEY, nil, Nod(OADD, nn, na))) // ...s[:n+argc]
	nx.Etype = 1
	l = list(l, Nod(OAS, ns, nx)) // s = s[:n+argc]

2956
	for a := n.List.Next; a != nil; a = a.Next {
2957
		nx = Nod(OINDEX, ns, nn) // s[n] ...
2958
		nx.Bounded = true
2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981
		l = list(l, Nod(OAS, nx, a.N)) // s[n] = arg
		if a.Next != nil {
			l = list(l, Nod(OAS, nn, Nod(OADD, nn, Nodintconst(1)))) // n = n + 1
		}
	}

	typechecklist(l, Etop)
	walkstmtlist(l)
	*init = concat(*init, l)
	return ns
}

// Lower copy(a, b) to a memmove call or a runtime call.
//
// init {
//   n := len(a)
//   if n > len(b) { n = len(b) }
//   memmove(a.ptr, b.ptr, n*sizeof(elem(a)))
// }
// n;
//
// Also works if b is a string.
//
2982
func copyany(n *Node, init **NodeList, runtimecall bool) *Node {
2983
	if haspointers(n.Left.Type.Type) {
2984
		fn := writebarrierfn("typedslicecopy", n.Left.Type, n.Right.Type)
2985 2986 2987
		return mkcall1(fn, n.Type, init, typename(n.Left.Type.Type), n.Left, n.Right)
	}

2988
	if runtimecall {
2989
		var fn *Node
2990 2991 2992 2993 2994
		if n.Right.Type.Etype == TSTRING {
			fn = syslook("slicestringcopy", 1)
		} else {
			fn = syslook("slicecopy", 1)
		}
2995
		substArgTypes(fn, n.Left.Type, n.Right.Type)
2996 2997 2998 2999 3000
		return mkcall1(fn, n.Type, init, n.Left, n.Right, Nodintconst(n.Left.Type.Type.Width))
	}

	walkexpr(&n.Left, init)
	walkexpr(&n.Right, init)
3001 3002
	nl := temp(n.Left.Type)
	nr := temp(n.Right.Type)
Russ Cox's avatar
Russ Cox committed
3003
	var l *NodeList
3004 3005 3006
	l = list(l, Nod(OAS, nl, n.Left))
	l = list(l, Nod(OAS, nr, n.Right))

3007 3008
	nfrm := Nod(OSPTR, nr, nil)
	nto := Nod(OSPTR, nl, nil)
3009

3010
	nlen := temp(Types[TINT])
3011 3012 3013 3014 3015

	// n = len(to)
	l = list(l, Nod(OAS, nlen, Nod(OLEN, nl, nil)))

	// if n > len(frm) { n = len(frm) }
3016
	nif := Nod(OIF, nil, nil)
3017

3018
	nif.Left = Nod(OGT, nlen, Nod(OLEN, nr, nil))
3019 3020 3021 3022
	nif.Nbody = list(nif.Nbody, Nod(OAS, nlen, Nod(OLEN, nr, nil)))
	l = list(l, nif)

	// Call memmove.
3023
	fn := syslook("memmove", 1)
3024

3025
	substArgTypes(fn, nl.Type.Type, nl.Type.Type)
3026
	nwid := temp(Types[TUINTPTR])
3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041
	l = list(l, Nod(OAS, nwid, conv(nlen, Types[TUINTPTR])))
	nwid = Nod(OMUL, nwid, Nodintconst(nl.Type.Type.Width))
	l = list(l, mkcall1(fn, nil, init, nto, nfrm, nwid))

	typechecklist(l, Etop)
	walkstmtlist(l)
	*init = concat(*init, l)
	return nlen
}

func eqfor(t *Type, needsize *int) *Node {
	// Should only arrive here with large memory or
	// a struct/array containing a non-memory field/element.
	// Small memory is handled inline, and single non-memory
	// is handled during type check (OCMPSTR etc).
3042
	a := algtype1(t, nil)
3043 3044

	if a != AMEM && a != -1 {
3045
		Fatalf("eqfor %v", t)
3046 3047 3048
	}

	if a == AMEM {
3049
		n := syslook("memequal", 1)
3050
		substArgTypes(n, t, t)
3051 3052 3053 3054
		*needsize = 1
		return n
	}

3055 3056
	sym := typesymprefix(".eq", t)
	n := newname(sym)
3057
	n.Class = PFUNC
3058
	ntype := Nod(OTFUNC, nil, nil)
3059 3060 3061 3062 3063 3064 3065 3066 3067 3068
	ntype.List = list(ntype.List, Nod(ODCLFIELD, nil, typenod(Ptrto(t))))
	ntype.List = list(ntype.List, Nod(ODCLFIELD, nil, typenod(Ptrto(t))))
	ntype.Rlist = list(ntype.Rlist, Nod(ODCLFIELD, nil, typenod(Types[TBOOL])))
	typecheck(&ntype, Etype)
	n.Type = ntype.Type
	*needsize = 0
	return n
}

func countfield(t *Type) int {
3069 3070
	n := 0
	for t1 := t.Type; t1 != nil; t1 = t1.Down {
3071 3072 3073 3074 3075 3076
		n++
	}
	return n
}

func walkcompare(np **Node, init **NodeList) {
3077
	n := *np
3078 3079 3080 3081 3082 3083 3084 3085

	// Given interface value l and concrete value r, rewrite
	//   l == r
	// to
	//   x, ok := l.(type(r)); ok && x == r
	// Handle != similarly.
	// This avoids the allocation that would be required
	// to convert r to l for comparison.
Russ Cox's avatar
Russ Cox committed
3086
	var l *Node
3087

Russ Cox's avatar
Russ Cox committed
3088
	var r *Node
3089
	if Isinter(n.Left.Type) && !Isinter(n.Right.Type) {
3090 3091
		l = n.Left
		r = n.Right
3092
	} else if !Isinter(n.Left.Type) && Isinter(n.Right.Type) {
3093 3094 3095 3096 3097
		l = n.Right
		r = n.Left
	}

	if l != nil {
3098
		x := temp(r.Type)
3099 3100 3101 3102 3103
		if haspointers(r.Type) {
			a := Nod(OAS, x, nil)
			typecheck(&a, Etop)
			*init = list(*init, a)
		}
3104
		ok := temp(Types[TBOOL])
3105 3106

		// l.(type(r))
3107
		a := Nod(ODOTTYPE, l, nil)
3108 3109 3110 3111

		a.Type = r.Type

		// x, ok := l.(type(r))
3112
		expr := Nod(OAS2, nil, nil)
3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125

		expr.List = list1(x)
		expr.List = list(expr.List, ok)
		expr.Rlist = list1(a)
		typecheck(&expr, Etop)
		walkexpr(&expr, init)

		if n.Op == OEQ {
			r = Nod(OANDAND, ok, Nod(OEQ, x, r))
		} else {
			r = Nod(OOROR, Nod(ONOT, ok, nil), Nod(ONE, x, r))
		}
		*init = list(*init, expr)
3126 3127
		finishcompare(np, n, r, init)
		return
3128 3129 3130 3131
	}

	// Must be comparison of array or struct.
	// Otherwise back end handles it.
3132
	t := n.Left.Type
3133 3134 3135 3136 3137 3138

	switch t.Etype {
	default:
		return

	case TARRAY:
3139
		if Isslice(t) {
3140 3141 3142 3143 3144 3145 3146
			return
		}

	case TSTRUCT:
		break
	}

3147
	cmpl := n.Left
3148 3149 3150
	for cmpl != nil && cmpl.Op == OCONVNOP {
		cmpl = cmpl.Left
	}
3151
	cmpr := n.Right
3152 3153 3154 3155
	for cmpr != nil && cmpr.Op == OCONVNOP {
		cmpr = cmpr.Left
	}

3156
	if !islvalue(cmpl) || !islvalue(cmpr) {
3157
		Fatalf("arguments of comparison must be lvalues - %v %v", cmpl, cmpr)
3158 3159 3160
	}

	l = temp(Ptrto(t))
3161
	a := Nod(OAS, l, Nod(OADDR, cmpl, nil))
3162 3163 3164 3165 3166 3167 3168 3169 3170 3171
	a.Right.Etype = 1 // addr does not escape
	typecheck(&a, Etop)
	*init = list(*init, a)

	r = temp(Ptrto(t))
	a = Nod(OAS, r, Nod(OADDR, cmpr, nil))
	a.Right.Etype = 1 // addr does not escape
	typecheck(&a, Etop)
	*init = list(*init, a)

3172
	var andor Op = OANDAND
3173 3174 3175 3176
	if n.Op == ONE {
		andor = OOROR
	}

3177
	var expr *Node
3178
	if t.Etype == TARRAY && t.Bound <= 4 && issimple[t.Type.Etype] {
3179 3180
		// Four or fewer elements of a basic type.
		// Unroll comparisons.
3181 3182 3183
		var li *Node
		var ri *Node
		for i := 0; int64(i) < t.Bound; i++ {
3184 3185
			li = Nod(OINDEX, l, Nodintconst(int64(i)))
			ri = Nod(OINDEX, r, Nodintconst(int64(i)))
3186
			a = Nod(n.Op, li, ri)
3187 3188 3189 3190 3191 3192 3193 3194
			if expr == nil {
				expr = a
			} else {
				expr = Nod(andor, expr, a)
			}
		}

		if expr == nil {
3195
			expr = Nodbool(n.Op == OEQ)
3196
		}
3197 3198
		finishcompare(np, n, expr, init)
		return
3199 3200 3201 3202 3203
	}

	if t.Etype == TSTRUCT && countfield(t) <= 4 {
		// Struct of four or fewer fields.
		// Inline comparisons.
3204 3205 3206
		var li *Node
		var ri *Node
		for t1 := t.Type; t1 != nil; t1 = t1.Down {
3207 3208 3209 3210 3211
			if isblanksym(t1.Sym) {
				continue
			}
			li = Nod(OXDOT, l, newname(t1.Sym))
			ri = Nod(OXDOT, r, newname(t1.Sym))
3212
			a = Nod(n.Op, li, ri)
3213 3214 3215 3216 3217 3218 3219 3220
			if expr == nil {
				expr = a
			} else {
				expr = Nod(andor, expr, a)
			}
		}

		if expr == nil {
3221
			expr = Nodbool(n.Op == OEQ)
3222
		}
3223 3224
		finishcompare(np, n, expr, init)
		return
3225 3226 3227
	}

	// Chose not to inline.  Call equality function directly.
3228 3229
	var needsize int
	call := Nod(OCALL, eqfor(t, &needsize), nil)
3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240

	call.List = list(call.List, l)
	call.List = list(call.List, r)
	if needsize != 0 {
		call.List = list(call.List, Nodintconst(t.Width))
	}
	r = call
	if n.Op != OEQ {
		r = Nod(ONOT, r, nil)
	}

3241 3242 3243 3244 3245 3246 3247 3248 3249 3250
	finishcompare(np, n, r, init)
	return
}

func finishcompare(np **Node, n, r *Node, init **NodeList) {
	// Using np here to avoid passing &r to typecheck.
	*np = r
	typecheck(np, Erv)
	walkexpr(np, init)
	r = *np
3251 3252 3253 3254
	if r.Type != n.Type {
		r = Nod(OCONVNOP, r, nil)
		r.Type = n.Type
		r.Typecheck = 1
3255
		*np = r
3256 3257 3258
	}
}

3259
func samecheap(a *Node, b *Node) bool {
3260 3261 3262 3263 3264
	var ar *Node
	var br *Node
	for a != nil && b != nil && a.Op == b.Op {
		switch a.Op {
		default:
3265
			return false
3266 3267

		case ONAME:
3268
			return a == b
3269

3270
		case ODOT, ODOTPTR:
3271 3272 3273
			ar = a.Right
			br = b.Right
			if ar.Op != ONAME || br.Op != ONAME || ar.Sym != br.Sym {
3274
				return false
3275 3276 3277 3278 3279
			}

		case OINDEX:
			ar = a.Right
			br = b.Right
3280
			if !Isconst(ar, CTINT) || !Isconst(br, CTINT) || Mpcmpfixfix(ar.Val().U.(*Mpint), br.Val().U.(*Mpint)) != 0 {
3281
				return false
3282 3283 3284 3285 3286 3287 3288
			}
		}

		a = a.Left
		b = b.Left
	}

3289
	return false
3290 3291 3292
}

func walkrotate(np **Node) {
3293
	if Thearch.Thechar == '0' || Thearch.Thechar == '7' || Thearch.Thechar == '9' {
3294 3295 3296
		return
	}

3297
	n := *np
3298 3299

	// Want << | >> or >> | << or << ^ >> or >> ^ << on unsigned value.
3300
	l := n.Left
3301

3302
	r := n.Right
3303
	if (n.Op != OOR && n.Op != OXOR) || (l.Op != OLSH && l.Op != ORSH) || (r.Op != OLSH && r.Op != ORSH) || n.Type == nil || Issigned[n.Type.Etype] || l.Op == r.Op {
3304 3305 3306 3307
		return
	}

	// Want same, side effect-free expression on lhs of both shifts.
3308
	if !samecheap(l.Left, r.Left) {
3309 3310 3311 3312
		return
	}

	// Constants adding to width?
3313
	w := int(l.Type.Width * 8)
3314

3315
	if Smallintconst(l.Right) && Smallintconst(r.Right) {
3316
		sl := int(Mpgetfix(l.Right.Val().U.(*Mpint)))
3317
		if sl >= 0 {
3318
			sr := int(Mpgetfix(r.Right.Val().U.(*Mpint)))
3319
			if sr >= 0 && sl+sr == w {
Russ Cox's avatar
Russ Cox committed
3320 3321 3322 3323 3324 3325 3326 3327 3328
				// Rewrite left shift half to left rotate.
				if l.Op == OLSH {
					n = l
				} else {
					n = r
				}
				n.Op = OLROT

				// Remove rotate 0 and rotate w.
3329
				s := int(Mpgetfix(n.Right.Val().U.(*Mpint)))
Russ Cox's avatar
Russ Cox committed
3330 3331 3332 3333 3334 3335 3336

				if s == 0 || s == w {
					n = n.Left
				}

				*np = n
				return
3337 3338 3339 3340 3341 3342 3343 3344 3345
			}
		}
		return
	}

	// TODO: Could allow s and 32-s if s is bounded (maybe s&31 and 32-s&31).
	return
}

3346
// walkmul rewrites integer multiplication by powers of two as shifts.
3347
func walkmul(np **Node, init **NodeList) {
3348
	n := *np
3349
	if !Isint[n.Type.Etype] {
3350 3351 3352
		return
	}

3353 3354
	var nr *Node
	var nl *Node
3355 3356 3357 3358 3359 3360 3361 3362 3363 3364
	if n.Right.Op == OLITERAL {
		nl = n.Left
		nr = n.Right
	} else if n.Left.Op == OLITERAL {
		nl = n.Right
		nr = n.Left
	} else {
		return
	}

3365
	neg := 0
3366 3367

	// x*0 is 0 (and side effects of x).
3368 3369
	var pow int
	var w int
3370
	if Mpgetfix(nr.Val().U.(*Mpint)) == 0 {
3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414
		cheapexpr(nl, init)
		Nodconst(n, n.Type, 0)
		goto ret
	}

	// nr is a constant.
	pow = powtwo(nr)

	if pow < 0 {
		return
	}
	if pow >= 1000 {
		// negative power of 2, like -16
		neg = 1

		pow -= 1000
	}

	w = int(nl.Type.Width * 8)
	if pow+1 >= w { // too big, shouldn't happen
		return
	}

	nl = cheapexpr(nl, init)

	if pow == 0 {
		// x*1 is x
		n = nl

		goto ret
	}

	n = Nod(OLSH, nl, Nodintconst(int64(pow)))

ret:
	if neg != 0 {
		n = Nod(OMINUS, n, nil)
	}

	typecheck(&n, Erv)
	walkexpr(&n, init)
	*np = n
}

3415 3416
// walkdiv rewrites division by a constant as less expensive
// operations.
3417 3418 3419 3420
func walkdiv(np **Node, init **NodeList) {
	// if >= 0, nr is 1<<pow // 1 if nr is negative.

	// TODO(minux)
3421
	if Thearch.Thechar == '0' || Thearch.Thechar == '7' || Thearch.Thechar == '9' {
3422 3423 3424
		return
	}

3425
	n := *np
3426 3427 3428 3429 3430
	if n.Right.Op != OLITERAL {
		return
	}

	// nr is a constant.
3431
	nl := cheapexpr(n.Left, init)
3432

3433
	nr := n.Right
3434 3435 3436

	// special cases of mod/div
	// by a constant
3437
	w := int(nl.Type.Width * 8)
3438

3439 3440
	s := 0            // 1 if nr is negative.
	pow := powtwo(nr) // if >= 0, nr is 1<<pow
3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453
	if pow >= 1000 {
		// negative power of 2
		s = 1

		pow -= 1000
	}

	if pow+1 >= w {
		// divisor too large.
		return
	}

	if pow < 0 {
Russ Cox's avatar
Russ Cox committed
3454 3455 3456 3457 3458 3459
		// try to do division by multiply by (2^w)/d
		// see hacker's delight chapter 10
		// TODO: support 64-bit magic multiply here.
		var m Magic
		m.W = w

3460
		if Issigned[nl.Type.Etype] {
3461
			m.Sd = Mpgetfix(nr.Val().U.(*Mpint))
Russ Cox's avatar
Russ Cox committed
3462 3463
			Smagic(&m)
		} else {
3464
			m.Ud = uint64(Mpgetfix(nr.Val().U.(*Mpint)))
Russ Cox's avatar
Russ Cox committed
3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487
			Umagic(&m)
		}

		if m.Bad != 0 {
			return
		}

		// We have a quick division method so use it
		// for modulo too.
		if n.Op == OMOD {
			// rewrite as A%B = A - (A/B*B).
			n1 := Nod(ODIV, nl, nr)

			n2 := Nod(OMUL, n1, nr)
			n = Nod(OSUB, nl, n2)
			goto ret
		}

		switch Simtype[nl.Type.Etype] {
		default:
			return

			// n1 = nl * magic >> w (HMUL)
3488
		case TUINT8, TUINT16, TUINT32:
Russ Cox's avatar
Russ Cox committed
3489 3490 3491
			nc := Nod(OXXX, nil, nil)

			Nodconst(nc, nl.Type, int64(m.Um))
3492
			n1 := Nod(OHMUL, nl, nc)
Russ Cox's avatar
Russ Cox committed
3493 3494 3495 3496 3497 3498 3499 3500
			typecheck(&n1, Erv)
			if m.Ua != 0 {
				// Select a Go type with (at least) twice the width.
				var twide *Type
				switch Simtype[nl.Type.Etype] {
				default:
					return

3501
				case TUINT8, TUINT16:
Russ Cox's avatar
Russ Cox committed
3502 3503 3504 3505 3506
					twide = Types[TUINT32]

				case TUINT32:
					twide = Types[TUINT64]

3507
				case TINT8, TINT16:
Russ Cox's avatar
Russ Cox committed
3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528 3529 3530 3531
					twide = Types[TINT32]

				case TINT32:
					twide = Types[TINT64]
				}

				// add numerator (might overflow).
				// n2 = (n1 + nl)
				n2 := Nod(OADD, conv(n1, twide), conv(nl, twide))

				// shift by m.s
				nc := Nod(OXXX, nil, nil)

				Nodconst(nc, Types[TUINT], int64(m.S))
				n = conv(Nod(ORSH, n2, nc), nl.Type)
			} else {
				// n = n1 >> m.s
				nc := Nod(OXXX, nil, nil)

				Nodconst(nc, Types[TUINT], int64(m.S))
				n = Nod(ORSH, n1, nc)
			}

			// n1 = nl * magic >> w
3532
		case TINT8, TINT16, TINT32:
Russ Cox's avatar
Russ Cox committed
3533 3534 3535
			nc := Nod(OXXX, nil, nil)

			Nodconst(nc, nl.Type, m.Sm)
3536
			n1 := Nod(OHMUL, nl, nc)
Russ Cox's avatar
Russ Cox committed
3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562
			typecheck(&n1, Erv)
			if m.Sm < 0 {
				// add the numerator.
				n1 = Nod(OADD, n1, nl)
			}

			// shift by m.s
			nc = Nod(OXXX, nil, nil)

			Nodconst(nc, Types[TUINT], int64(m.S))
			n2 := conv(Nod(ORSH, n1, nc), nl.Type)

			// add 1 iff n1 is negative.
			nc = Nod(OXXX, nil, nil)

			Nodconst(nc, Types[TUINT], int64(w)-1)
			n3 := Nod(ORSH, nl, nc) // n4 = -1 iff n1 is negative.
			n = Nod(OSUB, n2, n3)

			// apply sign.
			if m.Sd < 0 {
				n = Nod(OMINUS, n, nil)
			}
		}

		goto ret
3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580
	}

	switch pow {
	case 0:
		if n.Op == OMOD {
			// nl % 1 is zero.
			Nodconst(n, n.Type, 0)
		} else if s != 0 {
			// divide by -1
			n.Op = OMINUS

			n.Right = nil
		} else {
			// divide by 1
			n = nl
		}

	default:
3581
		if Issigned[n.Type.Etype] {
3582 3583 3584 3585
			if n.Op == OMOD {
				// signed modulo 2^pow is like ANDing
				// with the last pow bits, but if nl < 0,
				// nl & (2^pow-1) is (nl+1)%2^pow - 1.
3586
				nc := Nod(OXXX, nil, nil)
3587 3588

				Nodconst(nc, Types[Simtype[TUINT]], int64(w)-1)
3589
				n1 := Nod(ORSH, nl, nc) // n1 = -1 iff nl < 0.
3590 3591 3592 3593 3594
				if pow == 1 {
					typecheck(&n1, Erv)
					n1 = cheapexpr(n1, init)

					// n = (nl+ε)&1 -ε where ε=1 iff nl<0.
3595
					n2 := Nod(OSUB, nl, n1)
3596

3597
					nc := Nod(OXXX, nil, nil)
3598
					Nodconst(nc, nl.Type, 1)
3599
					n3 := Nod(OAND, n2, nc)
3600 3601 3602
					n = Nod(OADD, n3, n1)
				} else {
					// n = (nl+ε)&(nr-1) - ε where ε=2^pow-1 iff nl<0.
3603
					nc := Nod(OXXX, nil, nil)
3604 3605

					Nodconst(nc, nl.Type, (1<<uint(pow))-1)
3606
					n2 := Nod(OAND, n1, nc) // n2 = 2^pow-1 iff nl<0.
3607 3608 3609
					typecheck(&n2, Erv)
					n2 = cheapexpr(n2, init)

3610 3611
					n3 := Nod(OADD, nl, n2)
					n4 := Nod(OAND, n3, nc)
3612 3613 3614 3615 3616 3617 3618 3619
					n = Nod(OSUB, n4, n2)
				}

				break
			} else {
				// arithmetic right shift does not give the correct rounding.
				// if nl >= 0, nl >> n == nl / nr
				// if nl < 0, we want to add 2^n-1 first.
3620
				nc := Nod(OXXX, nil, nil)
3621 3622

				Nodconst(nc, Types[Simtype[TUINT]], int64(w)-1)
3623
				n1 := Nod(ORSH, nl, nc) // n1 = -1 iff nl < 0.
3624 3625 3626 3627 3628
				if pow == 1 {
					// nl+1 is nl-(-1)
					n.Left = Nod(OSUB, nl, n1)
				} else {
					// Do a logical right right on -1 to keep pow bits.
3629
					nc := Nod(OXXX, nil, nil)
3630 3631

					Nodconst(nc, Types[Simtype[TUINT]], int64(w)-int64(pow))
3632
					n2 := Nod(ORSH, conv(n1, tounsigned(nl.Type)), nc)
3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650
					n.Left = Nod(OADD, nl, conv(n2, nl.Type))
				}

				// n = (nl + 2^pow-1) >> pow
				n.Op = ORSH

				nc = Nod(OXXX, nil, nil)
				Nodconst(nc, Types[Simtype[TUINT]], int64(pow))
				n.Right = nc
				n.Typecheck = 0
			}

			if s != 0 {
				n = Nod(OMINUS, n, nil)
			}
			break
		}

3651
		nc := Nod(OXXX, nil, nil)
3652 3653 3654 3655
		if n.Op == OMOD {
			// n = nl & (nr-1)
			n.Op = OAND

3656
			Nodconst(nc, nl.Type, Mpgetfix(nr.Val().U.(*Mpint))-1)
3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676
		} else {
			// n = nl >> pow
			n.Op = ORSH

			Nodconst(nc, Types[Simtype[TUINT]], int64(pow))
		}

		n.Typecheck = 0
		n.Right = nc
	}

	goto ret

ret:
	typecheck(&n, Erv)
	walkexpr(&n, init)
	*np = n
}

// return 1 if integer n must be in range [0, max), 0 otherwise
3677
func bounded(n *Node, max int64) bool {
3678
	if n.Type == nil || !Isint[n.Type.Etype] {
3679
		return false
3680 3681
	}

3682
	sign := Issigned[n.Type.Etype]
3683
	bits := int32(8 * n.Type.Width)
3684

3685
	if Smallintconst(n) {
3686
		v := Mpgetfix(n.Val().U.(*Mpint))
3687
		return 0 <= v && v < max
3688 3689 3690 3691
	}

	switch n.Op {
	case OAND:
3692
		v := int64(-1)
3693
		if Smallintconst(n.Left) {
3694
			v = Mpgetfix(n.Left.Val().U.(*Mpint))
3695
		} else if Smallintconst(n.Right) {
3696
			v = Mpgetfix(n.Right.Val().U.(*Mpint))
3697 3698 3699
		}

		if 0 <= v && v < max {
3700
			return true
3701 3702 3703
		}

	case OMOD:
3704
		if !sign && Smallintconst(n.Right) {
3705
			v := Mpgetfix(n.Right.Val().U.(*Mpint))
3706
			if 0 <= v && v <= max {
3707
				return true
3708 3709 3710 3711
			}
		}

	case ODIV:
3712
		if !sign && Smallintconst(n.Right) {
3713
			v := Mpgetfix(n.Right.Val().U.(*Mpint))
3714 3715 3716 3717 3718 3719 3720
			for bits > 0 && v >= 2 {
				bits--
				v >>= 1
			}
		}

	case ORSH:
3721
		if !sign && Smallintconst(n.Right) {
3722
			v := Mpgetfix(n.Right.Val().U.(*Mpint))
3723
			if v > int64(bits) {
3724
				return true
3725 3726 3727 3728 3729
			}
			bits -= int32(v)
		}
	}

3730
	if !sign && bits <= 62 && 1<<uint(bits) <= max {
3731
		return true
3732 3733
	}

3734
	return false
3735 3736 3737
}

func usefield(n *Node) {
3738
	if obj.Fieldtrack_enabled == 0 {
3739 3740 3741 3742 3743
		return
	}

	switch n.Op {
	default:
3744
		Fatalf("usefield %v", Oconv(int(n.Op), 0))
3745

3746
	case ODOT, ODOTPTR:
3747 3748 3749
		break
	}

3750 3751 3752 3753
	t := n.Left.Type
	if Isptr[t.Etype] {
		t = t.Type
	}
3754
	field := dotField[typeSym{t.Orig, n.Right.Sym}]
3755
	if field == nil {
3756
		Fatalf("usefield %v %v without paramfld", n.Left.Type, n.Right.Sym)
3757
	}
3758
	if field.Note == nil || !strings.Contains(*field.Note, "go:\"track\"") {
3759 3760 3761 3762 3763 3764 3765 3766 3767
		return
	}

	// dedup on list
	if field.Lastfn == Curfn {
		return
	}
	field.Lastfn = Curfn
	field.Outer = n.Left.Type
3768
	if Isptr[field.Outer.Etype] {
3769 3770 3771 3772 3773 3774 3775 3776 3777
		field.Outer = field.Outer.Type
	}
	if field.Outer.Sym == nil {
		Yyerror("tracked field must be in named struct type")
	}
	if !exportname(field.Sym.Name) {
		Yyerror("tracked field must be exported (upper case)")
	}

3778
	Curfn.Func.Fieldtrack = append(Curfn.Func.Fieldtrack, field)
3779 3780
}

3781
func candiscardlist(l *NodeList) bool {
3782
	for ; l != nil; l = l.Next {
3783 3784
		if !candiscard(l.N) {
			return false
3785 3786
		}
	}
3787
	return true
3788 3789
}

3790
func candiscard(n *Node) bool {
3791
	if n == nil {
3792
		return true
3793 3794 3795 3796
	}

	switch n.Op {
	default:
3797
		return false
3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854

		// Discardable as long as the subpieces are.
	case ONAME,
		ONONAME,
		OTYPE,
		OPACK,
		OLITERAL,
		OADD,
		OSUB,
		OOR,
		OXOR,
		OADDSTR,
		OADDR,
		OANDAND,
		OARRAYBYTESTR,
		OARRAYRUNESTR,
		OSTRARRAYBYTE,
		OSTRARRAYRUNE,
		OCAP,
		OCMPIFACE,
		OCMPSTR,
		OCOMPLIT,
		OMAPLIT,
		OSTRUCTLIT,
		OARRAYLIT,
		OPTRLIT,
		OCONV,
		OCONVIFACE,
		OCONVNOP,
		ODOT,
		OEQ,
		ONE,
		OLT,
		OLE,
		OGT,
		OGE,
		OKEY,
		OLEN,
		OMUL,
		OLSH,
		ORSH,
		OAND,
		OANDNOT,
		ONEW,
		ONOT,
		OCOM,
		OPLUS,
		OMINUS,
		OOROR,
		OPAREN,
		ORUNESTR,
		OREAL,
		OIMAG,
		OCOMPLEX:
		break

		// Discardable as long as we know it's not division by zero.
3855
	case ODIV, OMOD:
3856
		if Isconst(n.Right, CTINT) && mpcmpfixc(n.Right.Val().U.(*Mpint), 0) != 0 {
3857 3858
			break
		}
3859
		if Isconst(n.Right, CTFLT) && mpcmpfltc(n.Right.Val().U.(*Mpflt), 0) != 0 {
3860 3861
			break
		}
3862
		return false
3863 3864

		// Discardable as long as we know it won't fail because of a bad size.
3865
	case OMAKECHAN, OMAKEMAP:
3866
		if Isconst(n.Left, CTINT) && mpcmpfixc(n.Left.Val().U.(*Mpint), 0) == 0 {
3867 3868
			break
		}
3869
		return false
3870 3871 3872

		// Difficult to tell what sizes are okay.
	case OMAKESLICE:
3873
		return false
3874 3875
	}

3876
	if !candiscard(n.Left) || !candiscard(n.Right) || !candiscardlist(n.Ninit) || !candiscardlist(n.Nbody) || !candiscardlist(n.List) || !candiscardlist(n.Rlist) {
3877
		return false
3878 3879
	}

3880
	return true
3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893
}

// rewrite
//	print(x, y, z)
// into
//	func(a1, a2, a3) {
//		print(a1, a2, a3)
//	}(x, y, z)
// and same for println.

var walkprintfunc_prgen int

func walkprintfunc(np **Node, init **NodeList) {
3894
	n := *np
3895 3896 3897 3898 3899 3900 3901

	if n.Ninit != nil {
		walkstmtlist(n.Ninit)
		*init = concat(*init, n.Ninit)
		n.Ninit = nil
	}

3902 3903
	t := Nod(OTFUNC, nil, nil)
	num := 0
Russ Cox's avatar
Russ Cox committed
3904
	var printargs *NodeList
3905 3906 3907
	var a *Node
	var buf string
	for l := n.List; l != nil; l = l.Next {
3908 3909 3910 3911 3912 3913 3914
		buf = fmt.Sprintf("a%d", num)
		num++
		a = Nod(ODCLFIELD, newname(Lookup(buf)), typenod(l.N.Type))
		t.List = list(t.List, a)
		printargs = list(printargs, a.Left)
	}

3915
	fn := Nod(ODCLFUNC, nil, nil)
3916 3917
	walkprintfunc_prgen++
	buf = fmt.Sprintf("print·%d", walkprintfunc_prgen)
3918 3919 3920 3921
	fn.Func.Nname = newname(Lookup(buf))
	fn.Func.Nname.Name.Defn = fn
	fn.Func.Nname.Name.Param.Ntype = t
	declare(fn.Func.Nname, PFUNC)
3922

3923
	oldfn := Curfn
3924 3925 3926
	Curfn = nil
	funchdr(fn)

3927
	a = Nod(n.Op, nil, nil)
3928 3929 3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941
	a.List = printargs
	typecheck(&a, Etop)
	walkstmt(&a)

	fn.Nbody = list1(a)

	funcbody(fn)

	typecheck(&fn, Etop)
	typechecklist(fn.Nbody, Etop)
	xtop = list(xtop, fn)
	Curfn = oldfn

	a = Nod(OCALL, nil, nil)
3942
	a.Left = fn.Func.Nname
3943 3944 3945 3946 3947
	a.List = n.List
	typecheck(&a, Etop)
	walkexpr(&a, init)
	*np = a
}