Source file src/pkg/cmd/compile/internal/gc/range.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package gc
     6	
     7	import (
     8		"cmd/compile/internal/types"
     9		"cmd/internal/sys"
    10		"unicode/utf8"
    11	)
    12	
    13	// range
    14	func typecheckrange(n *Node) {
    15		// Typechecking order is important here:
    16		// 0. first typecheck range expression (slice/map/chan),
    17		//	it is evaluated only once and so logically it is not part of the loop.
    18		// 1. typecheck produced values,
    19		//	this part can declare new vars and so it must be typechecked before body,
    20		//	because body can contain a closure that captures the vars.
    21		// 2. decldepth++ to denote loop body.
    22		// 3. typecheck body.
    23		// 4. decldepth--.
    24		typecheckrangeExpr(n)
    25	
    26		// second half of dance, the first half being typecheckrangeExpr
    27		n.SetTypecheck(1)
    28		ls := n.List.Slice()
    29		for i1, n1 := range ls {
    30			if n1.Typecheck() == 0 {
    31				ls[i1] = typecheck(ls[i1], ctxExpr|ctxAssign)
    32			}
    33		}
    34	
    35		decldepth++
    36		typecheckslice(n.Nbody.Slice(), ctxStmt)
    37		decldepth--
    38	}
    39	
    40	func typecheckrangeExpr(n *Node) {
    41		n.Right = typecheck(n.Right, ctxExpr)
    42	
    43		t := n.Right.Type
    44		if t == nil {
    45			return
    46		}
    47		// delicate little dance.  see typecheckas2
    48		ls := n.List.Slice()
    49		for i1, n1 := range ls {
    50			if n1.Name == nil || n1.Name.Defn != n {
    51				ls[i1] = typecheck(ls[i1], ctxExpr|ctxAssign)
    52			}
    53		}
    54	
    55		if t.IsPtr() && t.Elem().IsArray() {
    56			t = t.Elem()
    57		}
    58		n.Type = t
    59	
    60		var t1, t2 *types.Type
    61		toomany := false
    62		switch t.Etype {
    63		default:
    64			yyerrorl(n.Pos, "cannot range over %L", n.Right)
    65			return
    66	
    67		case TARRAY, TSLICE:
    68			t1 = types.Types[TINT]
    69			t2 = t.Elem()
    70	
    71		case TMAP:
    72			t1 = t.Key()
    73			t2 = t.Elem()
    74	
    75		case TCHAN:
    76			if !t.ChanDir().CanRecv() {
    77				yyerrorl(n.Pos, "invalid operation: range %v (receive from send-only type %v)", n.Right, n.Right.Type)
    78				return
    79			}
    80	
    81			t1 = t.Elem()
    82			t2 = nil
    83			if n.List.Len() == 2 {
    84				toomany = true
    85			}
    86	
    87		case TSTRING:
    88			t1 = types.Types[TINT]
    89			t2 = types.Runetype
    90		}
    91	
    92		if n.List.Len() > 2 || toomany {
    93			yyerrorl(n.Pos, "too many variables in range")
    94		}
    95	
    96		var v1, v2 *Node
    97		if n.List.Len() != 0 {
    98			v1 = n.List.First()
    99		}
   100		if n.List.Len() > 1 {
   101			v2 = n.List.Second()
   102		}
   103	
   104		// this is not only a optimization but also a requirement in the spec.
   105		// "if the second iteration variable is the blank identifier, the range
   106		// clause is equivalent to the same clause with only the first variable
   107		// present."
   108		if v2.isBlank() {
   109			if v1 != nil {
   110				n.List.Set1(v1)
   111			}
   112			v2 = nil
   113		}
   114	
   115		var why string
   116		if v1 != nil {
   117			if v1.Name != nil && v1.Name.Defn == n {
   118				v1.Type = t1
   119			} else if v1.Type != nil && assignop(t1, v1.Type, &why) == 0 {
   120				yyerrorl(n.Pos, "cannot assign type %v to %L in range%s", t1, v1, why)
   121			}
   122			checkassign(n, v1)
   123		}
   124	
   125		if v2 != nil {
   126			if v2.Name != nil && v2.Name.Defn == n {
   127				v2.Type = t2
   128			} else if v2.Type != nil && assignop(t2, v2.Type, &why) == 0 {
   129				yyerrorl(n.Pos, "cannot assign type %v to %L in range%s", t2, v2, why)
   130			}
   131			checkassign(n, v2)
   132		}
   133	}
   134	
   135	func cheapComputableIndex(width int64) bool {
   136		switch thearch.LinkArch.Family {
   137		// MIPS does not have R+R addressing
   138		// Arm64 may lack ability to generate this code in our assembler,
   139		// but the architecture supports it.
   140		case sys.PPC64, sys.S390X:
   141			return width == 1
   142		case sys.AMD64, sys.I386, sys.ARM64, sys.ARM:
   143			switch width {
   144			case 1, 2, 4, 8:
   145				return true
   146			}
   147		}
   148		return false
   149	}
   150	
   151	// walkrange transforms various forms of ORANGE into
   152	// simpler forms.  The result must be assigned back to n.
   153	// Node n may also be modified in place, and may also be
   154	// the returned node.
   155	func walkrange(n *Node) *Node {
   156		if isMapClear(n) {
   157			m := n.Right
   158			lno := setlineno(m)
   159			n = mapClear(m)
   160			lineno = lno
   161			return n
   162		}
   163	
   164		// variable name conventions:
   165		//	ohv1, hv1, hv2: hidden (old) val 1, 2
   166		//	ha, hit: hidden aggregate, iterator
   167		//	hn, hp: hidden len, pointer
   168		//	hb: hidden bool
   169		//	a, v1, v2: not hidden aggregate, val 1, 2
   170	
   171		t := n.Type
   172	
   173		a := n.Right
   174		lno := setlineno(a)
   175		n.Right = nil
   176	
   177		var v1, v2 *Node
   178		l := n.List.Len()
   179		if l > 0 {
   180			v1 = n.List.First()
   181		}
   182	
   183		if l > 1 {
   184			v2 = n.List.Second()
   185		}
   186	
   187		if v2.isBlank() {
   188			v2 = nil
   189		}
   190	
   191		if v1.isBlank() && v2 == nil {
   192			v1 = nil
   193		}
   194	
   195		if v1 == nil && v2 != nil {
   196			Fatalf("walkrange: v2 != nil while v1 == nil")
   197		}
   198	
   199		// n.List has no meaning anymore, clear it
   200		// to avoid erroneous processing by racewalk.
   201		n.List.Set(nil)
   202	
   203		var ifGuard *Node
   204	
   205		translatedLoopOp := OFOR
   206	
   207		var body []*Node
   208		var init []*Node
   209		switch t.Etype {
   210		default:
   211			Fatalf("walkrange")
   212	
   213		case TARRAY, TSLICE:
   214			if arrayClear(n, v1, v2, a) {
   215				lineno = lno
   216				return n
   217			}
   218	
   219			// orderstmt arranged for a copy of the array/slice variable if needed.
   220			ha := a
   221	
   222			hv1 := temp(types.Types[TINT])
   223			hn := temp(types.Types[TINT])
   224	
   225			init = append(init, nod(OAS, hv1, nil))
   226			init = append(init, nod(OAS, hn, nod(OLEN, ha, nil)))
   227	
   228			n.Left = nod(OLT, hv1, hn)
   229			n.Right = nod(OAS, hv1, nod(OADD, hv1, nodintconst(1)))
   230	
   231			// for range ha { body }
   232			if v1 == nil {
   233				break
   234			}
   235	
   236			// for v1 := range ha { body }
   237			if v2 == nil {
   238				body = []*Node{nod(OAS, v1, hv1)}
   239				break
   240			}
   241	
   242			// for v1, v2 := range ha { body }
   243			if cheapComputableIndex(n.Type.Elem().Width) {
   244				// v1, v2 = hv1, ha[hv1]
   245				tmp := nod(OINDEX, ha, hv1)
   246				tmp.SetBounded(true)
   247				// Use OAS2 to correctly handle assignments
   248				// of the form "v1, a[v1] := range".
   249				a := nod(OAS2, nil, nil)
   250				a.List.Set2(v1, v2)
   251				a.Rlist.Set2(hv1, tmp)
   252				body = []*Node{a}
   253				break
   254			}
   255	
   256			// TODO(austin): OFORUNTIL is a strange beast, but is
   257			// necessary for expressing the control flow we need
   258			// while also making "break" and "continue" work. It
   259			// would be nice to just lower ORANGE during SSA, but
   260			// racewalk needs to see many of the operations
   261			// involved in ORANGE's implementation. If racewalk
   262			// moves into SSA, consider moving ORANGE into SSA and
   263			// eliminating OFORUNTIL.
   264	
   265			// TODO(austin): OFORUNTIL inhibits bounds-check
   266			// elimination on the index variable (see #20711).
   267			// Enhance the prove pass to understand this.
   268			ifGuard = nod(OIF, nil, nil)
   269			ifGuard.Left = nod(OLT, hv1, hn)
   270			translatedLoopOp = OFORUNTIL
   271	
   272			hp := temp(types.NewPtr(n.Type.Elem()))
   273			tmp := nod(OINDEX, ha, nodintconst(0))
   274			tmp.SetBounded(true)
   275			init = append(init, nod(OAS, hp, nod(OADDR, tmp, nil)))
   276	
   277			// Use OAS2 to correctly handle assignments
   278			// of the form "v1, a[v1] := range".
   279			a := nod(OAS2, nil, nil)
   280			a.List.Set2(v1, v2)
   281			a.Rlist.Set2(hv1, nod(ODEREF, hp, nil))
   282			body = append(body, a)
   283	
   284			// Advance pointer as part of the late increment.
   285			//
   286			// This runs *after* the condition check, so we know
   287			// advancing the pointer is safe and won't go past the
   288			// end of the allocation.
   289			a = nod(OAS, hp, addptr(hp, t.Elem().Width))
   290			a = typecheck(a, ctxStmt)
   291			n.List.Set1(a)
   292	
   293		case TMAP:
   294			// orderstmt allocated the iterator for us.
   295			// we only use a once, so no copy needed.
   296			ha := a
   297	
   298			hit := prealloc[n]
   299			th := hit.Type
   300			n.Left = nil
   301			keysym := th.Field(0).Sym  // depends on layout of iterator struct.  See reflect.go:hiter
   302			elemsym := th.Field(1).Sym // ditto
   303	
   304			fn := syslook("mapiterinit")
   305	
   306			fn = substArgTypes(fn, t.Key(), t.Elem(), th)
   307			init = append(init, mkcall1(fn, nil, nil, typename(t), ha, nod(OADDR, hit, nil)))
   308			n.Left = nod(ONE, nodSym(ODOT, hit, keysym), nodnil())
   309	
   310			fn = syslook("mapiternext")
   311			fn = substArgTypes(fn, th)
   312			n.Right = mkcall1(fn, nil, nil, nod(OADDR, hit, nil))
   313	
   314			key := nodSym(ODOT, hit, keysym)
   315			key = nod(ODEREF, key, nil)
   316			if v1 == nil {
   317				body = nil
   318			} else if v2 == nil {
   319				body = []*Node{nod(OAS, v1, key)}
   320			} else {
   321				elem := nodSym(ODOT, hit, elemsym)
   322				elem = nod(ODEREF, elem, nil)
   323				a := nod(OAS2, nil, nil)
   324				a.List.Set2(v1, v2)
   325				a.Rlist.Set2(key, elem)
   326				body = []*Node{a}
   327			}
   328	
   329		case TCHAN:
   330			// orderstmt arranged for a copy of the channel variable.
   331			ha := a
   332	
   333			n.Left = nil
   334	
   335			hv1 := temp(t.Elem())
   336			hv1.SetTypecheck(1)
   337			if types.Haspointers(t.Elem()) {
   338				init = append(init, nod(OAS, hv1, nil))
   339			}
   340			hb := temp(types.Types[TBOOL])
   341	
   342			n.Left = nod(ONE, hb, nodbool(false))
   343			a := nod(OAS2RECV, nil, nil)
   344			a.SetTypecheck(1)
   345			a.List.Set2(hv1, hb)
   346			a.Rlist.Set1(nod(ORECV, ha, nil))
   347			n.Left.Ninit.Set1(a)
   348			if v1 == nil {
   349				body = nil
   350			} else {
   351				body = []*Node{nod(OAS, v1, hv1)}
   352			}
   353			// Zero hv1. This prevents hv1 from being the sole, inaccessible
   354			// reference to an otherwise GC-able value during the next channel receive.
   355			// See issue 15281.
   356			body = append(body, nod(OAS, hv1, nil))
   357	
   358		case TSTRING:
   359			// Transform string range statements like "for v1, v2 = range a" into
   360			//
   361			// ha := a
   362			// for hv1 := 0; hv1 < len(ha); {
   363			//   hv1t := hv1
   364			//   hv2 := rune(ha[hv1])
   365			//   if hv2 < utf8.RuneSelf {
   366			//      hv1++
   367			//   } else {
   368			//      hv2, hv1 = decoderune(ha, hv1)
   369			//   }
   370			//   v1, v2 = hv1t, hv2
   371			//   // original body
   372			// }
   373	
   374			// orderstmt arranged for a copy of the string variable.
   375			ha := a
   376	
   377			hv1 := temp(types.Types[TINT])
   378			hv1t := temp(types.Types[TINT])
   379			hv2 := temp(types.Runetype)
   380	
   381			// hv1 := 0
   382			init = append(init, nod(OAS, hv1, nil))
   383	
   384			// hv1 < len(ha)
   385			n.Left = nod(OLT, hv1, nod(OLEN, ha, nil))
   386	
   387			if v1 != nil {
   388				// hv1t = hv1
   389				body = append(body, nod(OAS, hv1t, hv1))
   390			}
   391	
   392			// hv2 := rune(ha[hv1])
   393			nind := nod(OINDEX, ha, hv1)
   394			nind.SetBounded(true)
   395			body = append(body, nod(OAS, hv2, conv(nind, types.Runetype)))
   396	
   397			// if hv2 < utf8.RuneSelf
   398			nif := nod(OIF, nil, nil)
   399			nif.Left = nod(OLT, hv2, nodintconst(utf8.RuneSelf))
   400	
   401			// hv1++
   402			nif.Nbody.Set1(nod(OAS, hv1, nod(OADD, hv1, nodintconst(1))))
   403	
   404			// } else {
   405			eif := nod(OAS2, nil, nil)
   406			nif.Rlist.Set1(eif)
   407	
   408			// hv2, hv1 = decoderune(ha, hv1)
   409			eif.List.Set2(hv2, hv1)
   410			fn := syslook("decoderune")
   411			eif.Rlist.Set1(mkcall1(fn, fn.Type.Results(), nil, ha, hv1))
   412	
   413			body = append(body, nif)
   414	
   415			if v1 != nil {
   416				if v2 != nil {
   417					// v1, v2 = hv1t, hv2
   418					a := nod(OAS2, nil, nil)
   419					a.List.Set2(v1, v2)
   420					a.Rlist.Set2(hv1t, hv2)
   421					body = append(body, a)
   422				} else {
   423					// v1 = hv1t
   424					body = append(body, nod(OAS, v1, hv1t))
   425				}
   426			}
   427		}
   428	
   429		n.Op = translatedLoopOp
   430		typecheckslice(init, ctxStmt)
   431	
   432		if ifGuard != nil {
   433			ifGuard.Ninit.Append(init...)
   434			ifGuard = typecheck(ifGuard, ctxStmt)
   435		} else {
   436			n.Ninit.Append(init...)
   437		}
   438	
   439		typecheckslice(n.Left.Ninit.Slice(), ctxStmt)
   440	
   441		n.Left = typecheck(n.Left, ctxExpr)
   442		n.Left = defaultlit(n.Left, nil)
   443		n.Right = typecheck(n.Right, ctxStmt)
   444		typecheckslice(body, ctxStmt)
   445		n.Nbody.Prepend(body...)
   446	
   447		if ifGuard != nil {
   448			ifGuard.Nbody.Set1(n)
   449			n = ifGuard
   450		}
   451	
   452		n = walkstmt(n)
   453	
   454		lineno = lno
   455		return n
   456	}
   457	
   458	// isMapClear checks if n is of the form:
   459	//
   460	// for k := range m {
   461	//   delete(m, k)
   462	// }
   463	//
   464	// where == for keys of map m is reflexive.
   465	func isMapClear(n *Node) bool {
   466		if Debug['N'] != 0 || instrumenting {
   467			return false
   468		}
   469	
   470		if n.Op != ORANGE || n.Type.Etype != TMAP || n.List.Len() != 1 {
   471			return false
   472		}
   473	
   474		k := n.List.First()
   475		if k == nil || k.isBlank() {
   476			return false
   477		}
   478	
   479		// Require k to be a new variable name.
   480		if k.Name == nil || k.Name.Defn != n {
   481			return false
   482		}
   483	
   484		if n.Nbody.Len() != 1 {
   485			return false
   486		}
   487	
   488		stmt := n.Nbody.First() // only stmt in body
   489		if stmt == nil || stmt.Op != ODELETE {
   490			return false
   491		}
   492	
   493		m := n.Right
   494		if !samesafeexpr(stmt.List.First(), m) || !samesafeexpr(stmt.List.Second(), k) {
   495			return false
   496		}
   497	
   498		// Keys where equality is not reflexive can not be deleted from maps.
   499		if !isreflexive(m.Type.Key()) {
   500			return false
   501		}
   502	
   503		return true
   504	}
   505	
   506	// mapClear constructs a call to runtime.mapclear for the map m.
   507	func mapClear(m *Node) *Node {
   508		t := m.Type
   509	
   510		// instantiate mapclear(typ *type, hmap map[any]any)
   511		fn := syslook("mapclear")
   512		fn = substArgTypes(fn, t.Key(), t.Elem())
   513		n := mkcall1(fn, nil, nil, typename(t), m)
   514	
   515		n = typecheck(n, ctxStmt)
   516		n = walkstmt(n)
   517	
   518		return n
   519	}
   520	
   521	// Lower n into runtime·memclr if possible, for
   522	// fast zeroing of slices and arrays (issue 5373).
   523	// Look for instances of
   524	//
   525	// for i := range a {
   526	// 	a[i] = zero
   527	// }
   528	//
   529	// in which the evaluation of a is side-effect-free.
   530	//
   531	// Parameters are as in walkrange: "for v1, v2 = range a".
   532	func arrayClear(n, v1, v2, a *Node) bool {
   533		if Debug['N'] != 0 || instrumenting {
   534			return false
   535		}
   536	
   537		if v1 == nil || v2 != nil {
   538			return false
   539		}
   540	
   541		if n.Nbody.Len() != 1 || n.Nbody.First() == nil {
   542			return false
   543		}
   544	
   545		stmt := n.Nbody.First() // only stmt in body
   546		if stmt.Op != OAS || stmt.Left.Op != OINDEX {
   547			return false
   548		}
   549	
   550		if !samesafeexpr(stmt.Left.Left, a) || !samesafeexpr(stmt.Left.Right, v1) {
   551			return false
   552		}
   553	
   554		elemsize := n.Type.Elem().Width
   555		if elemsize <= 0 || !isZero(stmt.Right) {
   556			return false
   557		}
   558	
   559		// Convert to
   560		// if len(a) != 0 {
   561		// 	hp = &a[0]
   562		// 	hn = len(a)*sizeof(elem(a))
   563		// 	memclr{NoHeap,Has}Pointers(hp, hn)
   564		// 	i = len(a) - 1
   565		// }
   566		n.Op = OIF
   567	
   568		n.Nbody.Set(nil)
   569		n.Left = nod(ONE, nod(OLEN, a, nil), nodintconst(0))
   570	
   571		// hp = &a[0]
   572		hp := temp(types.Types[TUNSAFEPTR])
   573	
   574		tmp := nod(OINDEX, a, nodintconst(0))
   575		tmp.SetBounded(true)
   576		tmp = nod(OADDR, tmp, nil)
   577		tmp = convnop(tmp, types.Types[TUNSAFEPTR])
   578		n.Nbody.Append(nod(OAS, hp, tmp))
   579	
   580		// hn = len(a) * sizeof(elem(a))
   581		hn := temp(types.Types[TUINTPTR])
   582	
   583		tmp = nod(OLEN, a, nil)
   584		tmp = nod(OMUL, tmp, nodintconst(elemsize))
   585		tmp = conv(tmp, types.Types[TUINTPTR])
   586		n.Nbody.Append(nod(OAS, hn, tmp))
   587	
   588		var fn *Node
   589		if a.Type.Elem().HasHeapPointer() {
   590			// memclrHasPointers(hp, hn)
   591			Curfn.Func.setWBPos(stmt.Pos)
   592			fn = mkcall("memclrHasPointers", nil, nil, hp, hn)
   593		} else {
   594			// memclrNoHeapPointers(hp, hn)
   595			fn = mkcall("memclrNoHeapPointers", nil, nil, hp, hn)
   596		}
   597	
   598		n.Nbody.Append(fn)
   599	
   600		// i = len(a) - 1
   601		v1 = nod(OAS, v1, nod(OSUB, nod(OLEN, a, nil), nodintconst(1)))
   602	
   603		n.Nbody.Append(v1)
   604	
   605		n.Left = typecheck(n.Left, ctxExpr)
   606		n.Left = defaultlit(n.Left, nil)
   607		typecheckslice(n.Nbody.Slice(), ctxStmt)
   608		n = walkstmt(n)
   609		return true
   610	}
   611	
   612	// addptr returns (*T)(uintptr(p) + n).
   613	func addptr(p *Node, n int64) *Node {
   614		t := p.Type
   615	
   616		p = nod(OCONVNOP, p, nil)
   617		p.Type = types.Types[TUINTPTR]
   618	
   619		p = nod(OADD, p, nodintconst(n))
   620	
   621		p = nod(OCONVNOP, p, nil)
   622		p.Type = t
   623	
   624		return p
   625	}
   626	

View as plain text