intrinsics.go

Documentation: golang.org/x/tools/go/pointer

     1  // Copyright 2013 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 pointer
     6  
     7  // This package defines the treatment of intrinsics, i.e. library
     8  // functions requiring special analytical treatment.
     9  //
    10  // Most of these are C or assembly functions, but even some Go
    11  // functions require may special treatment if the analysis completely
    12  // replaces the implementation of an API such as reflection.
    13  
    14  // TODO(adonovan): support a means of writing analytic summaries in
    15  // the target code, so that users can summarise the effects of their
    16  // own C functions using a snippet of Go.
    17  
    18  import (
    19  	"fmt"
    20  	"go/types"
    21  
    22  	"golang.org/x/tools/go/ssa"
    23  )
    24  
    25  // Instances of 'intrinsic' generate analysis constraints for calls to
    26  // intrinsic functions.
    27  // Implementations may exploit information from the calling site
    28  // via cgn.callersite; for shared contours this is nil.
    29  type intrinsic func(a *analysis, cgn *cgnode)
    30  
    31  // Initialized in explicit init() to defeat (spurious) initialization
    32  // cycle error.
    33  var intrinsicsByName = make(map[string]intrinsic)
    34  
    35  func init() {
    36  	// Key strings are from Function.String().
    37  	// That little dot ۰ is an Arabic zero numeral (U+06F0),
    38  	// categories [Nd].
    39  	for name, fn := range map[string]intrinsic{
    40  		// Other packages.
    41  		"bytes.Equal":                  ext۰NoEffect,
    42  		"bytes.IndexByte":              ext۰NoEffect,
    43  		"crypto/aes.decryptBlockAsm":   ext۰NoEffect,
    44  		"crypto/aes.encryptBlockAsm":   ext۰NoEffect,
    45  		"crypto/aes.expandKeyAsm":      ext۰NoEffect,
    46  		"crypto/aes.hasAsm":            ext۰NoEffect,
    47  		"crypto/md5.block":             ext۰NoEffect,
    48  		"crypto/rc4.xorKeyStream":      ext۰NoEffect,
    49  		"crypto/sha1.block":            ext۰NoEffect,
    50  		"crypto/sha256.block":          ext۰NoEffect,
    51  		"hash/crc32.castagnoliSSE42":   ext۰NoEffect,
    52  		"hash/crc32.haveSSE42":         ext۰NoEffect,
    53  		"math.Abs":                     ext۰NoEffect,
    54  		"math.Acos":                    ext۰NoEffect,
    55  		"math.Asin":                    ext۰NoEffect,
    56  		"math.Atan":                    ext۰NoEffect,
    57  		"math.Atan2":                   ext۰NoEffect,
    58  		"math.Ceil":                    ext۰NoEffect,
    59  		"math.Cos":                     ext۰NoEffect,
    60  		"math.Dim":                     ext۰NoEffect,
    61  		"math.Exp":                     ext۰NoEffect,
    62  		"math.Exp2":                    ext۰NoEffect,
    63  		"math.Expm1":                   ext۰NoEffect,
    64  		"math.Float32bits":             ext۰NoEffect,
    65  		"math.Float32frombits":         ext۰NoEffect,
    66  		"math.Float64bits":             ext۰NoEffect,
    67  		"math.Float64frombits":         ext۰NoEffect,
    68  		"math.Floor":                   ext۰NoEffect,
    69  		"math.Frexp":                   ext۰NoEffect,
    70  		"math.Hypot":                   ext۰NoEffect,
    71  		"math.Ldexp":                   ext۰NoEffect,
    72  		"math.Log":                     ext۰NoEffect,
    73  		"math.Log10":                   ext۰NoEffect,
    74  		"math.Log1p":                   ext۰NoEffect,
    75  		"math.Log2":                    ext۰NoEffect,
    76  		"math.Max":                     ext۰NoEffect,
    77  		"math.Min":                     ext۰NoEffect,
    78  		"math.Mod":                     ext۰NoEffect,
    79  		"math.Modf":                    ext۰NoEffect,
    80  		"math.Remainder":               ext۰NoEffect,
    81  		"math.Sin":                     ext۰NoEffect,
    82  		"math.Sincos":                  ext۰NoEffect,
    83  		"math.Sqrt":                    ext۰NoEffect,
    84  		"math.Tan":                     ext۰NoEffect,
    85  		"math.Trunc":                   ext۰NoEffect,
    86  		"math/big.addMulVVW":           ext۰NoEffect,
    87  		"math/big.addVV":               ext۰NoEffect,
    88  		"math/big.addVW":               ext۰NoEffect,
    89  		"math/big.bitLen":              ext۰NoEffect,
    90  		"math/big.divWVW":              ext۰NoEffect,
    91  		"math/big.divWW":               ext۰NoEffect,
    92  		"math/big.mulAddVWW":           ext۰NoEffect,
    93  		"math/big.mulWW":               ext۰NoEffect,
    94  		"math/big.shlVU":               ext۰NoEffect,
    95  		"math/big.shrVU":               ext۰NoEffect,
    96  		"math/big.subVV":               ext۰NoEffect,
    97  		"math/big.subVW":               ext۰NoEffect,
    98  		"net.runtime_Semacquire":       ext۰NoEffect,
    99  		"net.runtime_Semrelease":       ext۰NoEffect,
   100  		"net.runtime_pollClose":        ext۰NoEffect,
   101  		"net.runtime_pollOpen":         ext۰NoEffect,
   102  		"net.runtime_pollReset":        ext۰NoEffect,
   103  		"net.runtime_pollServerInit":   ext۰NoEffect,
   104  		"net.runtime_pollSetDeadline":  ext۰NoEffect,
   105  		"net.runtime_pollUnblock":      ext۰NoEffect,
   106  		"net.runtime_pollWait":         ext۰NoEffect,
   107  		"net.runtime_pollWaitCanceled": ext۰NoEffect,
   108  		"os.epipecheck":                ext۰NoEffect,
   109  		// All other runtime functions are treated as NoEffect.
   110  		"runtime.SetFinalizer":              ext۰runtime۰SetFinalizer,
   111  		"strings.IndexByte":                 ext۰NoEffect,
   112  		"sync.runtime_Semacquire":           ext۰NoEffect,
   113  		"sync.runtime_Semrelease":           ext۰NoEffect,
   114  		"sync.runtime_Syncsemacquire":       ext۰NoEffect,
   115  		"sync.runtime_Syncsemcheck":         ext۰NoEffect,
   116  		"sync.runtime_Syncsemrelease":       ext۰NoEffect,
   117  		"sync.runtime_procPin":              ext۰NoEffect,
   118  		"sync.runtime_procUnpin":            ext۰NoEffect,
   119  		"sync.runtime_registerPool":         ext۰NoEffect,
   120  		"sync/atomic.AddInt32":              ext۰NoEffect,
   121  		"sync/atomic.AddInt64":              ext۰NoEffect,
   122  		"sync/atomic.AddUint32":             ext۰NoEffect,
   123  		"sync/atomic.AddUint64":             ext۰NoEffect,
   124  		"sync/atomic.AddUintptr":            ext۰NoEffect,
   125  		"sync/atomic.CompareAndSwapInt32":   ext۰NoEffect,
   126  		"sync/atomic.CompareAndSwapUint32":  ext۰NoEffect,
   127  		"sync/atomic.CompareAndSwapUint64":  ext۰NoEffect,
   128  		"sync/atomic.CompareAndSwapUintptr": ext۰NoEffect,
   129  		"sync/atomic.LoadInt32":             ext۰NoEffect,
   130  		"sync/atomic.LoadInt64":             ext۰NoEffect,
   131  		"sync/atomic.LoadPointer":           ext۰NoEffect, // ignore unsafe.Pointers
   132  		"sync/atomic.LoadUint32":            ext۰NoEffect,
   133  		"sync/atomic.LoadUint64":            ext۰NoEffect,
   134  		"sync/atomic.LoadUintptr":           ext۰NoEffect,
   135  		"sync/atomic.StoreInt32":            ext۰NoEffect,
   136  		"sync/atomic.StorePointer":          ext۰NoEffect, // ignore unsafe.Pointers
   137  		"sync/atomic.StoreUint32":           ext۰NoEffect,
   138  		"sync/atomic.StoreUintptr":          ext۰NoEffect,
   139  		"syscall.Close":                     ext۰NoEffect,
   140  		"syscall.Exit":                      ext۰NoEffect,
   141  		"syscall.Getpid":                    ext۰NoEffect,
   142  		"syscall.Getwd":                     ext۰NoEffect,
   143  		"syscall.Kill":                      ext۰NoEffect,
   144  		"syscall.RawSyscall":                ext۰NoEffect,
   145  		"syscall.RawSyscall6":               ext۰NoEffect,
   146  		"syscall.Syscall":                   ext۰NoEffect,
   147  		"syscall.Syscall6":                  ext۰NoEffect,
   148  		"syscall.runtime_AfterFork":         ext۰NoEffect,
   149  		"syscall.runtime_BeforeFork":        ext۰NoEffect,
   150  		"syscall.setenv_c":                  ext۰NoEffect,
   151  		"time.Sleep":                        ext۰NoEffect,
   152  		"time.now":                          ext۰NoEffect,
   153  		"time.startTimer":                   ext۰time۰startTimer,
   154  		"time.stopTimer":                    ext۰NoEffect,
   155  	} {
   156  		intrinsicsByName[name] = fn
   157  	}
   158  }
   159  
   160  // findIntrinsic returns the constraint generation function for an
   161  // intrinsic function fn, or nil if the function should be handled normally.
   162  func (a *analysis) findIntrinsic(fn *ssa.Function) intrinsic {
   163  	// Consult the *Function-keyed cache.
   164  	// A cached nil indicates a normal non-intrinsic function.
   165  	impl, ok := a.intrinsics[fn]
   166  	if !ok {
   167  		impl = intrinsicsByName[fn.String()] // may be nil
   168  
   169  		if a.isReflect(fn) {
   170  			if !a.config.Reflection {
   171  				impl = ext۰NoEffect // reflection disabled
   172  			} else if impl == nil {
   173  				// Ensure all "reflect" code is treated intrinsically.
   174  				impl = ext۰NotYetImplemented
   175  			}
   176  		} else if impl == nil && fn.Pkg != nil && fn.Pkg.Pkg.Path() == "runtime" {
   177  			// Ignore "runtime" (except SetFinalizer):
   178  			// it has few interesting effects on aliasing
   179  			// and is full of unsafe code we can't analyze.
   180  			impl = ext۰NoEffect
   181  		}
   182  
   183  		a.intrinsics[fn] = impl
   184  	}
   185  	return impl
   186  }
   187  
   188  // isReflect reports whether fn belongs to the "reflect" package.
   189  func (a *analysis) isReflect(fn *ssa.Function) bool {
   190  	if a.reflectValueObj == nil {
   191  		return false // "reflect" package not loaded
   192  	}
   193  	reflectPackage := a.reflectValueObj.Pkg()
   194  	if fn.Pkg != nil && fn.Pkg.Pkg == reflectPackage {
   195  		return true
   196  	}
   197  	// Synthetic wrappers have a nil Pkg, so they slip through the
   198  	// previous check.  Check the receiver package.
   199  	// TODO(adonovan): should synthetic wrappers have a non-nil Pkg?
   200  	if recv := fn.Signature.Recv(); recv != nil {
   201  		if named, ok := deref(recv.Type()).(*types.Named); ok {
   202  			if named.Obj().Pkg() == reflectPackage {
   203  				return true // e.g. wrapper of (reflect.Value).f
   204  			}
   205  		}
   206  	}
   207  	return false
   208  }
   209  
   210  // A trivial intrinsic suitable for any function that does not:
   211  // 1) induce aliases between its arguments or any global variables;
   212  // 2) call any functions; or
   213  // 3) create any labels.
   214  //
   215  // Many intrinsics (such as CompareAndSwapInt32) have a fourth kind of
   216  // effect: loading or storing through a pointer.  Though these could
   217  // be significant, we deliberately ignore them because they are
   218  // generally not worth the effort.
   219  //
   220  // We sometimes violate condition #3 if the function creates only
   221  // non-function labels, as the control-flow graph is still sound.
   222  func ext۰NoEffect(a *analysis, cgn *cgnode) {}
   223  
   224  func ext۰NotYetImplemented(a *analysis, cgn *cgnode) {
   225  	fn := cgn.fn
   226  	a.warnf(fn.Pos(), "unsound: intrinsic treatment of %s not yet implemented", fn)
   227  }
   228  
   229  // ---------- func runtime.SetFinalizer(x, f interface{}) ----------
   230  
   231  // runtime.SetFinalizer(x, f)
   232  type runtimeSetFinalizerConstraint struct {
   233  	targets nodeid // (indirect)
   234  	f       nodeid // (ptr)
   235  	x       nodeid
   236  }
   237  
   238  func (c *runtimeSetFinalizerConstraint) ptr() nodeid { return c.f }
   239  func (c *runtimeSetFinalizerConstraint) presolve(h *hvn) {
   240  	h.markIndirect(onodeid(c.targets), "SetFinalizer.targets")
   241  }
   242  func (c *runtimeSetFinalizerConstraint) renumber(mapping []nodeid) {
   243  	c.targets = mapping[c.targets]
   244  	c.f = mapping[c.f]
   245  	c.x = mapping[c.x]
   246  }
   247  
   248  func (c *runtimeSetFinalizerConstraint) String() string {
   249  	return fmt.Sprintf("runtime.SetFinalizer(n%d, n%d)", c.x, c.f)
   250  }
   251  
   252  func (c *runtimeSetFinalizerConstraint) solve(a *analysis, delta *nodeset) {
   253  	for _, fObj := range delta.AppendTo(a.deltaSpace) {
   254  		tDyn, f, indirect := a.taggedValue(nodeid(fObj))
   255  		if indirect {
   256  			// TODO(adonovan): we'll need to implement this
   257  			// when we start creating indirect tagged objects.
   258  			panic("indirect tagged object")
   259  		}
   260  
   261  		tSig, ok := tDyn.Underlying().(*types.Signature)
   262  		if !ok {
   263  			continue // not a function
   264  		}
   265  		if tSig.Recv() != nil {
   266  			panic(tSig)
   267  		}
   268  		if tSig.Params().Len() != 1 {
   269  			continue //  not a unary function
   270  		}
   271  
   272  		// Extract x to tmp.
   273  		tx := tSig.Params().At(0).Type()
   274  		tmp := a.addNodes(tx, "SetFinalizer.tmp")
   275  		a.typeAssert(tx, tmp, c.x, false)
   276  
   277  		// Call f(tmp).
   278  		a.store(f, tmp, 1, a.sizeof(tx))
   279  
   280  		// Add dynamic call target.
   281  		if a.onlineCopy(c.targets, f) {
   282  			a.addWork(c.targets)
   283  		}
   284  	}
   285  }
   286  
   287  func ext۰runtime۰SetFinalizer(a *analysis, cgn *cgnode) {
   288  	// This is the shared contour, used for dynamic calls.
   289  	targets := a.addOneNode(tInvalid, "SetFinalizer.targets", nil)
   290  	cgn.sites = append(cgn.sites, &callsite{targets: targets})
   291  	params := a.funcParams(cgn.obj)
   292  	a.addConstraint(&runtimeSetFinalizerConstraint{
   293  		targets: targets,
   294  		x:       params,
   295  		f:       params + 1,
   296  	})
   297  }
   298  
   299  // ---------- func time.startTimer(t *runtimeTimer) ----------
   300  
   301  // time.StartTimer(t)
   302  type timeStartTimerConstraint struct {
   303  	targets nodeid // (indirect)
   304  	t       nodeid // (ptr)
   305  }
   306  
   307  func (c *timeStartTimerConstraint) ptr() nodeid { return c.t }
   308  func (c *timeStartTimerConstraint) presolve(h *hvn) {
   309  	h.markIndirect(onodeid(c.targets), "StartTimer.targets")
   310  }
   311  func (c *timeStartTimerConstraint) renumber(mapping []nodeid) {
   312  	c.targets = mapping[c.targets]
   313  	c.t = mapping[c.t]
   314  }
   315  
   316  func (c *timeStartTimerConstraint) String() string {
   317  	return fmt.Sprintf("time.startTimer(n%d)", c.t)
   318  }
   319  
   320  func (c *timeStartTimerConstraint) solve(a *analysis, delta *nodeset) {
   321  	for _, tObj := range delta.AppendTo(a.deltaSpace) {
   322  		t := nodeid(tObj)
   323  
   324  		// We model startTimer as if it was defined thus:
   325  		// 	func startTimer(t *runtimeTimer) { t.f(t.arg) }
   326  
   327  		// We hard-code the field offsets of time.runtimeTimer:
   328  		// type runtimeTimer struct {
   329  		//  0     __identity__
   330  		//  1    i      int32
   331  		//  2    when   int64
   332  		//  3    period int64
   333  		//  4    f      func(int64, interface{})
   334  		//  5    arg    interface{}
   335  		// }
   336  		f := t + 4
   337  		arg := t + 5
   338  
   339  		// store t.arg to t.f.params[0]
   340  		// (offset 1 => skip identity)
   341  		a.store(f, arg, 1, 1)
   342  
   343  		// Add dynamic call target.
   344  		if a.onlineCopy(c.targets, f) {
   345  			a.addWork(c.targets)
   346  		}
   347  	}
   348  }
   349  
   350  func ext۰time۰startTimer(a *analysis, cgn *cgnode) {
   351  	// This is the shared contour, used for dynamic calls.
   352  	targets := a.addOneNode(tInvalid, "startTimer.targets", nil)
   353  	cgn.sites = append(cgn.sites, &callsite{targets: targets})
   354  	params := a.funcParams(cgn.obj)
   355  	a.addConstraint(&timeStartTimerConstraint{
   356  		targets: targets,
   357  		t:       params,
   358  	})
   359  }
   360
View as plain text