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 walk
     6  
     7  import (
     8  	"unicode/utf8"
     9  
    10  	"cmd/compile/internal/base"
    11  	"cmd/compile/internal/ir"
    12  	"cmd/compile/internal/reflectdata"
    13  	"cmd/compile/internal/ssagen"
    14  	"cmd/compile/internal/typecheck"
    15  	"cmd/compile/internal/types"
    16  	"cmd/internal/sys"
    17  )
    18  
    19  func cheapComputableIndex(width int64) bool {
    20  	switch ssagen.Arch.LinkArch.Family {
    21  	// MIPS does not have R+R addressing
    22  	// Arm64 may lack ability to generate this code in our assembler,
    23  	// but the architecture supports it.
    24  	case sys.PPC64, sys.S390X:
    25  		return width == 1
    26  	case sys.AMD64, sys.I386, sys.ARM64, sys.ARM:
    27  		switch width {
    28  		case 1, 2, 4, 8:
    29  			return true
    30  		}
    31  	}
    32  	return false
    33  }
    34  
    35  // walkRange transforms various forms of ORANGE into
    36  // simpler forms.  The result must be assigned back to n.
    37  // Node n may also be modified in place, and may also be
    38  // the returned node.
    39  func walkRange(nrange *ir.RangeStmt) ir.Node {
    40  	if isMapClear(nrange) {
    41  		m := nrange.X
    42  		lno := ir.SetPos(m)
    43  		n := mapClear(m)
    44  		base.Pos = lno
    45  		return n
    46  	}
    47  
    48  	nfor := ir.NewForStmt(nrange.Pos(), nil, nil, nil, nil)
    49  	nfor.SetInit(nrange.Init())
    50  	nfor.Label = nrange.Label
    51  
    52  	// variable name conventions:
    53  	//	ohv1, hv1, hv2: hidden (old) val 1, 2
    54  	//	ha, hit: hidden aggregate, iterator
    55  	//	hn, hp: hidden len, pointer
    56  	//	hb: hidden bool
    57  	//	a, v1, v2: not hidden aggregate, val 1, 2
    58  
    59  	a := nrange.X
    60  	t := typecheck.RangeExprType(a.Type())
    61  	lno := ir.SetPos(a)
    62  
    63  	v1, v2 := nrange.Key, nrange.Value
    64  
    65  	if ir.IsBlank(v2) {
    66  		v2 = nil
    67  	}
    68  
    69  	if ir.IsBlank(v1) && v2 == nil {
    70  		v1 = nil
    71  	}
    72  
    73  	if v1 == nil && v2 != nil {
    74  		base.Fatalf("walkRange: v2 != nil while v1 == nil")
    75  	}
    76  
    77  	var ifGuard *ir.IfStmt
    78  
    79  	var body []ir.Node
    80  	var init []ir.Node
    81  	switch t.Kind() {
    82  	default:
    83  		base.Fatalf("walkRange")
    84  
    85  	case types.TARRAY, types.TSLICE:
    86  		if nn := arrayClear(nrange, v1, v2, a); nn != nil {
    87  			base.Pos = lno
    88  			return nn
    89  		}
    90  
    91  		// order.stmt arranged for a copy of the array/slice variable if needed.
    92  		ha := a
    93  
    94  		hv1 := typecheck.Temp(types.Types[types.TINT])
    95  		hn := typecheck.Temp(types.Types[types.TINT])
    96  
    97  		init = append(init, ir.NewAssignStmt(base.Pos, hv1, nil))
    98  		init = append(init, ir.NewAssignStmt(base.Pos, hn, ir.NewUnaryExpr(base.Pos, ir.OLEN, ha)))
    99  
   100  		nfor.Cond = ir.NewBinaryExpr(base.Pos, ir.OLT, hv1, hn)
   101  		nfor.Post = ir.NewAssignStmt(base.Pos, hv1, ir.NewBinaryExpr(base.Pos, ir.OADD, hv1, ir.NewInt(1)))
   102  
   103  		// for range ha { body }
   104  		if v1 == nil {
   105  			break
   106  		}
   107  
   108  		// for v1 := range ha { body }
   109  		if v2 == nil {
   110  			body = []ir.Node{ir.NewAssignStmt(base.Pos, v1, hv1)}
   111  			break
   112  		}
   113  
   114  		// for v1, v2 := range ha { body }
   115  		if cheapComputableIndex(t.Elem().Size()) {
   116  			// v1, v2 = hv1, ha[hv1]
   117  			tmp := ir.NewIndexExpr(base.Pos, ha, hv1)
   118  			tmp.SetBounded(true)
   119  			// Use OAS2 to correctly handle assignments
   120  			// of the form "v1, a[v1] := range".
   121  			a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{v1, v2}, []ir.Node{hv1, tmp})
   122  			body = []ir.Node{a}
   123  			break
   124  		}
   125  
   126  		// TODO(austin): OFORUNTIL is a strange beast, but is
   127  		// necessary for expressing the control flow we need
   128  		// while also making "break" and "continue" work. It
   129  		// would be nice to just lower ORANGE during SSA, but
   130  		// racewalk needs to see many of the operations
   131  		// involved in ORANGE's implementation. If racewalk
   132  		// moves into SSA, consider moving ORANGE into SSA and
   133  		// eliminating OFORUNTIL.
   134  
   135  		// TODO(austin): OFORUNTIL inhibits bounds-check
   136  		// elimination on the index variable (see #20711).
   137  		// Enhance the prove pass to understand this.
   138  		ifGuard = ir.NewIfStmt(base.Pos, nil, nil, nil)
   139  		ifGuard.Cond = ir.NewBinaryExpr(base.Pos, ir.OLT, hv1, hn)
   140  		nfor.SetOp(ir.OFORUNTIL)
   141  
   142  		hp := typecheck.Temp(types.NewPtr(t.Elem()))
   143  		tmp := ir.NewIndexExpr(base.Pos, ha, ir.NewInt(0))
   144  		tmp.SetBounded(true)
   145  		init = append(init, ir.NewAssignStmt(base.Pos, hp, typecheck.NodAddr(tmp)))
   146  
   147  		// Use OAS2 to correctly handle assignments
   148  		// of the form "v1, a[v1] := range".
   149  		a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{v1, v2}, []ir.Node{hv1, ir.NewStarExpr(base.Pos, hp)})
   150  		body = append(body, a)
   151  
   152  		// Advance pointer as part of the late increment.
   153  		//
   154  		// This runs *after* the condition check, so we know
   155  		// advancing the pointer is safe and won't go past the
   156  		// end of the allocation.
   157  		as := ir.NewAssignStmt(base.Pos, hp, addptr(hp, t.Elem().Size()))
   158  		nfor.Late = []ir.Node{typecheck.Stmt(as)}
   159  
   160  	case types.TMAP:
   161  		// order.stmt allocated the iterator for us.
   162  		// we only use a once, so no copy needed.
   163  		ha := a
   164  
   165  		hit := nrange.Prealloc
   166  		th := hit.Type()
   167  		// depends on layout of iterator struct.
   168  		// See cmd/compile/internal/reflectdata/reflect.go:MapIterType
   169  		keysym := th.Field(0).Sym
   170  		elemsym := th.Field(1).Sym // ditto
   171  
   172  		fn := typecheck.LookupRuntime("mapiterinit")
   173  
   174  		fn = typecheck.SubstArgTypes(fn, t.Key(), t.Elem(), th)
   175  		init = append(init, mkcallstmt1(fn, reflectdata.TypePtr(t), ha, typecheck.NodAddr(hit)))
   176  		nfor.Cond = ir.NewBinaryExpr(base.Pos, ir.ONE, ir.NewSelectorExpr(base.Pos, ir.ODOT, hit, keysym), typecheck.NodNil())
   177  
   178  		fn = typecheck.LookupRuntime("mapiternext")
   179  		fn = typecheck.SubstArgTypes(fn, th)
   180  		nfor.Post = mkcallstmt1(fn, typecheck.NodAddr(hit))
   181  
   182  		key := ir.NewStarExpr(base.Pos, ir.NewSelectorExpr(base.Pos, ir.ODOT, hit, keysym))
   183  		if v1 == nil {
   184  			body = nil
   185  		} else if v2 == nil {
   186  			body = []ir.Node{ir.NewAssignStmt(base.Pos, v1, key)}
   187  		} else {
   188  			elem := ir.NewStarExpr(base.Pos, ir.NewSelectorExpr(base.Pos, ir.ODOT, hit, elemsym))
   189  			a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{v1, v2}, []ir.Node{key, elem})
   190  			body = []ir.Node{a}
   191  		}
   192  
   193  	case types.TCHAN:
   194  		// order.stmt arranged for a copy of the channel variable.
   195  		ha := a
   196  
   197  		hv1 := typecheck.Temp(t.Elem())
   198  		hv1.SetTypecheck(1)
   199  		if t.Elem().HasPointers() {
   200  			init = append(init, ir.NewAssignStmt(base.Pos, hv1, nil))
   201  		}
   202  		hb := typecheck.Temp(types.Types[types.TBOOL])
   203  
   204  		nfor.Cond = ir.NewBinaryExpr(base.Pos, ir.ONE, hb, ir.NewBool(false))
   205  		lhs := []ir.Node{hv1, hb}
   206  		rhs := []ir.Node{ir.NewUnaryExpr(base.Pos, ir.ORECV, ha)}
   207  		a := ir.NewAssignListStmt(base.Pos, ir.OAS2RECV, lhs, rhs)
   208  		a.SetTypecheck(1)
   209  		nfor.Cond = ir.InitExpr([]ir.Node{a}, nfor.Cond)
   210  		if v1 == nil {
   211  			body = nil
   212  		} else {
   213  			body = []ir.Node{ir.NewAssignStmt(base.Pos, v1, hv1)}
   214  		}
   215  		// Zero hv1. This prevents hv1 from being the sole, inaccessible
   216  		// reference to an otherwise GC-able value during the next channel receive.
   217  		// See issue 15281.
   218  		body = append(body, ir.NewAssignStmt(base.Pos, hv1, nil))
   219  
   220  	case types.TSTRING:
   221  		// Transform string range statements like "for v1, v2 = range a" into
   222  		//
   223  		// ha := a
   224  		// for hv1 := 0; hv1 < len(ha); {
   225  		//   hv1t := hv1
   226  		//   hv2 := rune(ha[hv1])
   227  		//   if hv2 < utf8.RuneSelf {
   228  		//      hv1++
   229  		//   } else {
   230  		//      hv2, hv1 = decoderune(ha, hv1)
   231  		//   }
   232  		//   v1, v2 = hv1t, hv2
   233  		//   // original body
   234  		// }
   235  
   236  		// order.stmt arranged for a copy of the string variable.
   237  		ha := a
   238  
   239  		hv1 := typecheck.Temp(types.Types[types.TINT])
   240  		hv1t := typecheck.Temp(types.Types[types.TINT])
   241  		hv2 := typecheck.Temp(types.RuneType)
   242  
   243  		// hv1 := 0
   244  		init = append(init, ir.NewAssignStmt(base.Pos, hv1, nil))
   245  
   246  		// hv1 < len(ha)
   247  		nfor.Cond = ir.NewBinaryExpr(base.Pos, ir.OLT, hv1, ir.NewUnaryExpr(base.Pos, ir.OLEN, ha))
   248  
   249  		if v1 != nil {
   250  			// hv1t = hv1
   251  			body = append(body, ir.NewAssignStmt(base.Pos, hv1t, hv1))
   252  		}
   253  
   254  		// hv2 := rune(ha[hv1])
   255  		nind := ir.NewIndexExpr(base.Pos, ha, hv1)
   256  		nind.SetBounded(true)
   257  		body = append(body, ir.NewAssignStmt(base.Pos, hv2, typecheck.Conv(nind, types.RuneType)))
   258  
   259  		// if hv2 < utf8.RuneSelf
   260  		nif := ir.NewIfStmt(base.Pos, nil, nil, nil)
   261  		nif.Cond = ir.NewBinaryExpr(base.Pos, ir.OLT, hv2, ir.NewInt(utf8.RuneSelf))
   262  
   263  		// hv1++
   264  		nif.Body = []ir.Node{ir.NewAssignStmt(base.Pos, hv1, ir.NewBinaryExpr(base.Pos, ir.OADD, hv1, ir.NewInt(1)))}
   265  
   266  		// } else {
   267  		// hv2, hv1 = decoderune(ha, hv1)
   268  		fn := typecheck.LookupRuntime("decoderune")
   269  		call := mkcall1(fn, fn.Type().Results(), &nif.Else, ha, hv1)
   270  		a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{hv2, hv1}, []ir.Node{call})
   271  		nif.Else.Append(a)
   272  
   273  		body = append(body, nif)
   274  
   275  		if v1 != nil {
   276  			if v2 != nil {
   277  				// v1, v2 = hv1t, hv2
   278  				a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{v1, v2}, []ir.Node{hv1t, hv2})
   279  				body = append(body, a)
   280  			} else {
   281  				// v1 = hv1t
   282  				body = append(body, ir.NewAssignStmt(base.Pos, v1, hv1t))
   283  			}
   284  		}
   285  	}
   286  
   287  	typecheck.Stmts(init)
   288  
   289  	if ifGuard != nil {
   290  		ifGuard.PtrInit().Append(init...)
   291  		ifGuard = typecheck.Stmt(ifGuard).(*ir.IfStmt)
   292  	} else {
   293  		nfor.PtrInit().Append(init...)
   294  	}
   295  
   296  	typecheck.Stmts(nfor.Cond.Init())
   297  
   298  	nfor.Cond = typecheck.Expr(nfor.Cond)
   299  	nfor.Cond = typecheck.DefaultLit(nfor.Cond, nil)
   300  	nfor.Post = typecheck.Stmt(nfor.Post)
   301  	typecheck.Stmts(body)
   302  	nfor.Body.Append(body...)
   303  	nfor.Body.Append(nrange.Body...)
   304  
   305  	var n ir.Node = nfor
   306  	if ifGuard != nil {
   307  		ifGuard.Body = []ir.Node{n}
   308  		n = ifGuard
   309  	}
   310  
   311  	n = walkStmt(n)
   312  
   313  	base.Pos = lno
   314  	return n
   315  }
   316  
   317  // isMapClear checks if n is of the form:
   318  //
   319  // for k := range m {
   320  //   delete(m, k)
   321  // }
   322  //
   323  // where == for keys of map m is reflexive.
   324  func isMapClear(n *ir.RangeStmt) bool {
   325  	if base.Flag.N != 0 || base.Flag.Cfg.Instrumenting {
   326  		return false
   327  	}
   328  
   329  	t := n.X.Type()
   330  	if n.Op() != ir.ORANGE || t.Kind() != types.TMAP || n.Key == nil || n.Value != nil {
   331  		return false
   332  	}
   333  
   334  	k := n.Key
   335  	// Require k to be a new variable name.
   336  	if !ir.DeclaredBy(k, n) {
   337  		return false
   338  	}
   339  
   340  	if len(n.Body) != 1 {
   341  		return false
   342  	}
   343  
   344  	stmt := n.Body[0] // only stmt in body
   345  	if stmt == nil || stmt.Op() != ir.ODELETE {
   346  		return false
   347  	}
   348  
   349  	m := n.X
   350  	if delete := stmt.(*ir.CallExpr); !ir.SameSafeExpr(delete.Args[0], m) || !ir.SameSafeExpr(delete.Args[1], k) {
   351  		return false
   352  	}
   353  
   354  	// Keys where equality is not reflexive can not be deleted from maps.
   355  	if !types.IsReflexive(t.Key()) {
   356  		return false
   357  	}
   358  
   359  	return true
   360  }
   361  
   362  // mapClear constructs a call to runtime.mapclear for the map m.
   363  func mapClear(m ir.Node) ir.Node {
   364  	t := m.Type()
   365  
   366  	// instantiate mapclear(typ *type, hmap map[any]any)
   367  	fn := typecheck.LookupRuntime("mapclear")
   368  	fn = typecheck.SubstArgTypes(fn, t.Key(), t.Elem())
   369  	n := mkcallstmt1(fn, reflectdata.TypePtr(t), m)
   370  	return walkStmt(typecheck.Stmt(n))
   371  }
   372  
   373  // Lower n into runtime·memclr if possible, for
   374  // fast zeroing of slices and arrays (issue 5373).
   375  // Look for instances of
   376  //
   377  // for i := range a {
   378  // 	a[i] = zero
   379  // }
   380  //
   381  // in which the evaluation of a is side-effect-free.
   382  //
   383  // Parameters are as in walkRange: "for v1, v2 = range a".
   384  func arrayClear(loop *ir.RangeStmt, v1, v2, a ir.Node) ir.Node {
   385  	if base.Flag.N != 0 || base.Flag.Cfg.Instrumenting {
   386  		return nil
   387  	}
   388  
   389  	if v1 == nil || v2 != nil {
   390  		return nil
   391  	}
   392  
   393  	if len(loop.Body) != 1 || loop.Body[0] == nil {
   394  		return nil
   395  	}
   396  
   397  	stmt1 := loop.Body[0] // only stmt in body
   398  	if stmt1.Op() != ir.OAS {
   399  		return nil
   400  	}
   401  	stmt := stmt1.(*ir.AssignStmt)
   402  	if stmt.X.Op() != ir.OINDEX {
   403  		return nil
   404  	}
   405  	lhs := stmt.X.(*ir.IndexExpr)
   406  
   407  	if !ir.SameSafeExpr(lhs.X, a) || !ir.SameSafeExpr(lhs.Index, v1) {
   408  		return nil
   409  	}
   410  
   411  	elemsize := typecheck.RangeExprType(loop.X.Type()).Elem().Size()
   412  	if elemsize <= 0 || !ir.IsZero(stmt.Y) {
   413  		return nil
   414  	}
   415  
   416  	// Convert to
   417  	// if len(a) != 0 {
   418  	// 	hp = &a[0]
   419  	// 	hn = len(a)*sizeof(elem(a))
   420  	// 	memclr{NoHeap,Has}Pointers(hp, hn)
   421  	// 	i = len(a) - 1
   422  	// }
   423  	n := ir.NewIfStmt(base.Pos, nil, nil, nil)
   424  	n.Cond = ir.NewBinaryExpr(base.Pos, ir.ONE, ir.NewUnaryExpr(base.Pos, ir.OLEN, a), ir.NewInt(0))
   425  
   426  	// hp = &a[0]
   427  	hp := typecheck.Temp(types.Types[types.TUNSAFEPTR])
   428  
   429  	ix := ir.NewIndexExpr(base.Pos, a, ir.NewInt(0))
   430  	ix.SetBounded(true)
   431  	addr := typecheck.ConvNop(typecheck.NodAddr(ix), types.Types[types.TUNSAFEPTR])
   432  	n.Body.Append(ir.NewAssignStmt(base.Pos, hp, addr))
   433  
   434  	// hn = len(a) * sizeof(elem(a))
   435  	hn := typecheck.Temp(types.Types[types.TUINTPTR])
   436  	mul := typecheck.Conv(ir.NewBinaryExpr(base.Pos, ir.OMUL, ir.NewUnaryExpr(base.Pos, ir.OLEN, a), ir.NewInt(elemsize)), types.Types[types.TUINTPTR])
   437  	n.Body.Append(ir.NewAssignStmt(base.Pos, hn, mul))
   438  
   439  	var fn ir.Node
   440  	if a.Type().Elem().HasPointers() {
   441  		// memclrHasPointers(hp, hn)
   442  		ir.CurFunc.SetWBPos(stmt.Pos())
   443  		fn = mkcallstmt("memclrHasPointers", hp, hn)
   444  	} else {
   445  		// memclrNoHeapPointers(hp, hn)
   446  		fn = mkcallstmt("memclrNoHeapPointers", hp, hn)
   447  	}
   448  
   449  	n.Body.Append(fn)
   450  
   451  	// i = len(a) - 1
   452  	v1 = ir.NewAssignStmt(base.Pos, v1, ir.NewBinaryExpr(base.Pos, ir.OSUB, ir.NewUnaryExpr(base.Pos, ir.OLEN, a), ir.NewInt(1)))
   453  
   454  	n.Body.Append(v1)
   455  
   456  	n.Cond = typecheck.Expr(n.Cond)
   457  	n.Cond = typecheck.DefaultLit(n.Cond, nil)
   458  	typecheck.Stmts(n.Body)
   459  	return walkStmt(n)
   460  }
   461  
   462  // addptr returns (*T)(uintptr(p) + n).
   463  func addptr(p ir.Node, n int64) ir.Node {
   464  	t := p.Type()
   465  
   466  	p = ir.NewConvExpr(base.Pos, ir.OCONVNOP, nil, p)
   467  	p.SetType(types.Types[types.TUINTPTR])
   468  
   469  	p = ir.NewBinaryExpr(base.Pos, ir.OADD, p, ir.NewInt(n))
   470  
   471  	p = ir.NewConvExpr(base.Pos, ir.OCONVNOP, nil, p)
   472  	p.SetType(t)
   473  
   474  	return p
   475  }
   476
View as plain text