Source file src/cmd/compile/internal/ssa/prove.go

     1  // Copyright 2016 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 ssa
     6  
     7  import (
     8  	"cmd/compile/internal/ssa/block"
     9  	"cmd/compile/internal/types"
    10  	"cmd/internal/src"
    11  	"fmt"
    12  	"math"
    13  	"math/bits"
    14  	"strings"
    15  )
    16  
    17  type branch int
    18  
    19  const (
    20  	unknown branch = iota
    21  	positive
    22  	negative
    23  	// The outedges from a jump table are jumpTable0,
    24  	// jumpTable0+1, jumpTable0+2, etc. There could be an
    25  	// arbitrary number so we can't list them all here.
    26  	jumpTable0
    27  )
    28  
    29  func (b branch) String() string {
    30  	switch b {
    31  	case unknown:
    32  		return "unk"
    33  	case positive:
    34  		return "pos"
    35  	case negative:
    36  		return "neg"
    37  	default:
    38  		return fmt.Sprintf("jmp%d", b-jumpTable0)
    39  	}
    40  }
    41  
    42  // relation represents the set of possible relations between
    43  // pairs of variables (v, w). Without a priori knowledge the
    44  // mask is lt | eq | gt meaning v can be less than, equal to or
    45  // greater than w. When the execution path branches on the condition
    46  // `v op w` the set of relations is updated to exclude any
    47  // relation not possible due to `v op w` being true (or false).
    48  //
    49  // E.g.
    50  //
    51  //	r := relation(...)
    52  //
    53  //	if v < w {
    54  //	  newR := r & lt
    55  //	}
    56  //	if v >= w {
    57  //	  newR := r & (eq|gt)
    58  //	}
    59  //	if v != w {
    60  //	  newR := r & (lt|gt)
    61  //	}
    62  type relation uint
    63  
    64  const (
    65  	lt relation = 1 << iota
    66  	eq
    67  	gt
    68  )
    69  
    70  var relationStrings = [...]string{
    71  	0: "none", lt: "<", eq: "==", lt | eq: "<=",
    72  	gt: ">", gt | lt: "!=", gt | eq: ">=", gt | eq | lt: "any",
    73  }
    74  
    75  func (r relation) String() string {
    76  	if r < relation(len(relationStrings)) {
    77  		return relationStrings[r]
    78  	}
    79  	return fmt.Sprintf("relation(%d)", uint(r))
    80  }
    81  
    82  // domain represents the domain of a variable pair in which a set
    83  // of relations is known. For example, relations learned for unsigned
    84  // pairs cannot be transferred to signed pairs because the same bit
    85  // representation can mean something else.
    86  type domain uint
    87  
    88  const (
    89  	signed domain = 1 << iota
    90  	unsigned
    91  	pointer
    92  	boolean
    93  )
    94  
    95  var domainStrings = [...]string{
    96  	"signed", "unsigned", "pointer", "boolean",
    97  }
    98  
    99  func (d domain) String() string {
   100  	s := ""
   101  	for i, ds := range domainStrings {
   102  		if d&(1<<uint(i)) != 0 {
   103  			if len(s) != 0 {
   104  				s += "|"
   105  			}
   106  			s += ds
   107  			d &^= 1 << uint(i)
   108  		}
   109  	}
   110  	if d != 0 {
   111  		if len(s) != 0 {
   112  			s += "|"
   113  		}
   114  		s += fmt.Sprintf("0x%x", uint(d))
   115  	}
   116  	return s
   117  }
   118  
   119  // a limit records known upper and lower bounds for a value.
   120  //
   121  // If we have min>max or umin>umax, then this limit is
   122  // called "unsatisfiable". When we encounter such a limit, we
   123  // know that any code for which that limit applies is unreachable.
   124  // We don't particularly care how unsatisfiable limits propagate,
   125  // including becoming satisfiable, because any optimization
   126  // decisions based on those limits only apply to unreachable code.
   127  type limit struct {
   128  	min, max   int64  // min <= value <= max, signed
   129  	umin, umax uint64 // umin <= value <= umax, unsigned
   130  	// For booleans, we use 0==false, 1==true for both ranges
   131  	// For pointers, we use 0,0,0,0 for nil and minInt64,maxInt64,1,maxUint64 for nonnil
   132  }
   133  
   134  func (l limit) String() string {
   135  	return fmt.Sprintf("sm,SM=%d,%d um,UM=%d,%d", l.min, l.max, l.umin, l.umax)
   136  }
   137  
   138  func (l limit) intersect(l2 limit) limit {
   139  	l.min = max(l.min, l2.min)
   140  	l.umin = max(l.umin, l2.umin)
   141  	l.max = min(l.max, l2.max)
   142  	l.umax = min(l.umax, l2.umax)
   143  	return l
   144  }
   145  
   146  func (l limit) signedMin(m int64) limit {
   147  	l.min = max(l.min, m)
   148  	return l
   149  }
   150  
   151  func (l limit) signedMinMax(minimum, maximum int64) limit {
   152  	l.min = max(l.min, minimum)
   153  	l.max = min(l.max, maximum)
   154  	return l
   155  }
   156  
   157  func (l limit) unsignedMin(m uint64) limit {
   158  	l.umin = max(l.umin, m)
   159  	return l
   160  }
   161  func (l limit) unsignedMax(m uint64) limit {
   162  	l.umax = min(l.umax, m)
   163  	return l
   164  }
   165  func (l limit) unsignedMinMax(minimum, maximum uint64) limit {
   166  	l.umin = max(l.umin, minimum)
   167  	l.umax = min(l.umax, maximum)
   168  	return l
   169  }
   170  
   171  func (l limit) nonzero() bool {
   172  	return l.min > 0 || l.umin > 0 || l.max < 0
   173  }
   174  func (l limit) maybeZero() bool {
   175  	return !l.nonzero()
   176  }
   177  func (l limit) nonnegative() bool {
   178  	return l.min >= 0
   179  }
   180  func (l limit) unsat() bool {
   181  	return l.min > l.max || l.umin > l.umax
   182  }
   183  
   184  // If x and y can add without overflow or underflow
   185  // (using b bits), safeAdd returns x+y, true.
   186  // Otherwise, returns 0, false.
   187  func safeAdd(x, y int64, b uint) (int64, bool) {
   188  	s := x + y
   189  	if x >= 0 && y >= 0 && s < 0 {
   190  		return 0, false // 64-bit overflow
   191  	}
   192  	if x < 0 && y < 0 && s >= 0 {
   193  		return 0, false // 64-bit underflow
   194  	}
   195  	if !fitsInBits(s, b) {
   196  		return 0, false
   197  	}
   198  	return s, true
   199  }
   200  
   201  // same as safeAdd for unsigned arithmetic.
   202  func safeAddU(x, y uint64, b uint) (uint64, bool) {
   203  	s := x + y
   204  	if s < x || s < y {
   205  		return 0, false // 64-bit overflow
   206  	}
   207  	if !fitsInBitsU(s, b) {
   208  		return 0, false
   209  	}
   210  	return s, true
   211  }
   212  
   213  // same as safeAdd but for subtraction.
   214  func safeSub(x, y int64, b uint) (int64, bool) {
   215  	if y == math.MinInt64 {
   216  		if x == math.MaxInt64 {
   217  			return 0, false // 64-bit overflow
   218  		}
   219  		x++
   220  		y++
   221  	}
   222  	return safeAdd(x, -y, b)
   223  }
   224  
   225  // same as safeAddU but for subtraction.
   226  func safeSubU(x, y uint64, b uint) (uint64, bool) {
   227  	if x < y {
   228  		return 0, false // 64-bit underflow
   229  	}
   230  	s := x - y
   231  	if !fitsInBitsU(s, b) {
   232  		return 0, false
   233  	}
   234  	return s, true
   235  }
   236  
   237  // fitsInBits reports whether x fits in b bits (signed).
   238  func fitsInBits(x int64, b uint) bool {
   239  	if b == 64 {
   240  		return true
   241  	}
   242  	m := int64(-1) << (b - 1)
   243  	M := -m - 1
   244  	return x >= m && x <= M
   245  }
   246  
   247  // fitsInBitsU reports whether x fits in b bits (unsigned).
   248  func fitsInBitsU(x uint64, b uint) bool {
   249  	return x>>b == 0
   250  }
   251  
   252  func noLimit() limit {
   253  	return noLimitForBitsize(64)
   254  }
   255  
   256  func noLimitForBitsize(bitsize uint) limit {
   257  	return limit{min: -(1 << (bitsize - 1)), max: 1<<(bitsize-1) - 1, umin: 0, umax: 1<<bitsize - 1}
   258  }
   259  
   260  func convertIntWithBitsize[Target uint64 | int64, Source uint64 | int64](x Source, bitsize uint) Target {
   261  	if Target(0)-1 < 0 {
   262  		// Signed target: sign-extend the low bitsize bits.
   263  		switch bitsize {
   264  		case 64:
   265  			return Target(int64(x))
   266  		case 32:
   267  			return Target(int32(x))
   268  		case 16:
   269  			return Target(int16(x))
   270  		case 8:
   271  			return Target(int8(x))
   272  		}
   273  	} else {
   274  		// Unsigned target: zero-extend the low bitsize bits.
   275  		switch bitsize {
   276  		case 64:
   277  			return Target(uint64(x))
   278  		case 32:
   279  			return Target(uint32(x))
   280  		case 16:
   281  			return Target(uint16(x))
   282  		case 8:
   283  			return Target(uint8(x))
   284  		}
   285  	}
   286  	panic("unreachable")
   287  }
   288  
   289  // unsignedFixedLeadingBits extracts the all the most significant fixed bits from the limit.
   290  // fixed and count are an other way to represent a limit, you can convert them to a limit as follows:
   291  //
   292  //	umin = fixed
   293  //	umax = fixed | (1<<(64-count) - 1)
   294  //
   295  // In order to be useful for bitmanip analysis fixed and count are a coarser tool than a limit:
   296  // 1. the varying section (umax-umin) is always one less than a power of two
   297  // 2. that section is naturally aligned inside the 64-bit space
   298  func (l limit) unsignedFixedLeadingBits() (fixed uint64, count uint) {
   299  	varying := uint(bits.Len64(l.umin ^ l.umax))
   300  	count = uint(bits.LeadingZeros64(l.umin ^ l.umax))
   301  	fixed = l.umin &^ (1<<varying - 1)
   302  	return
   303  }
   304  
   305  // add returns the limit obtained by adding a value with limit l
   306  // to a value with limit l2. The result must fit in b bits.
   307  func (l limit) add(l2 limit, b uint) limit {
   308  	var isLConst, isL2Const bool
   309  	var lConst, l2Const uint64
   310  	if l.min == l.max {
   311  		isLConst = true
   312  		lConst = convertIntWithBitsize[uint64](l.min, b)
   313  	} else if l.umin == l.umax {
   314  		isLConst = true
   315  		lConst = l.umin
   316  	}
   317  	if l2.min == l2.max {
   318  		isL2Const = true
   319  		l2Const = convertIntWithBitsize[uint64](l2.min, b)
   320  	} else if l2.umin == l2.umax {
   321  		isL2Const = true
   322  		l2Const = l2.umin
   323  	}
   324  	if isLConst && isL2Const {
   325  		r := lConst + l2Const
   326  		r &= (uint64(1) << b) - 1
   327  		int64r := convertIntWithBitsize[int64](r, b)
   328  		return limit{min: int64r, max: int64r, umin: r, umax: r}
   329  	}
   330  
   331  	r := noLimit()
   332  	min, minOk := safeAdd(l.min, l2.min, b)
   333  	max, maxOk := safeAdd(l.max, l2.max, b)
   334  	if minOk && maxOk {
   335  		r.min = min
   336  		r.max = max
   337  	}
   338  	umin, uminOk := safeAddU(l.umin, l2.umin, b)
   339  	umax, umaxOk := safeAddU(l.umax, l2.umax, b)
   340  	if uminOk && umaxOk {
   341  		r.umin = umin
   342  		r.umax = umax
   343  	}
   344  	return r
   345  }
   346  
   347  // same as add but for subtraction.
   348  func (l limit) sub(l2 limit, b uint) limit {
   349  	r := noLimit()
   350  	min, minOk := safeSub(l.min, l2.max, b)
   351  	max, maxOk := safeSub(l.max, l2.min, b)
   352  	if minOk && maxOk {
   353  		r.min = min
   354  		r.max = max
   355  	}
   356  	umin, uminOk := safeSubU(l.umin, l2.umax, b)
   357  	umax, umaxOk := safeSubU(l.umax, l2.umin, b)
   358  	if uminOk && umaxOk {
   359  		r.umin = umin
   360  		r.umax = umax
   361  	}
   362  	return r
   363  }
   364  
   365  // same as add but for multiplication.
   366  func (l limit) mul(l2 limit, b uint) limit {
   367  	r := noLimit()
   368  	umaxhi, umaxlo := bits.Mul64(l.umax, l2.umax)
   369  	if umaxhi == 0 && fitsInBitsU(umaxlo, b) {
   370  		r.umax = umaxlo
   371  		r.umin = l.umin * l2.umin
   372  		// Note: if the code containing this multiply is
   373  		// unreachable, then we may have umin>umax, and this
   374  		// multiply may overflow.  But that's ok for
   375  		// unreachable code. If this code is reachable, we
   376  		// know umin<=umax, so this multiply will not overflow
   377  		// because the max multiply didn't.
   378  	}
   379  	// Signed is harder, so don't bother. The only useful
   380  	// case is when we know both multiplicands are nonnegative,
   381  	// but that case is handled above because we would have then
   382  	// previously propagated signed info to the unsigned domain,
   383  	// and will propagate it back after the multiply.
   384  	return r
   385  }
   386  
   387  // Similar to add, but compute 1 << l if it fits without overflow in b bits.
   388  func (l limit) exp2(b uint) limit {
   389  	r := noLimit()
   390  	if l.umax < uint64(b) {
   391  		r.umin = 1 << l.umin
   392  		r.umax = 1 << l.umax
   393  		// Same as above in mul, signed<->unsigned propagation
   394  		// will handle the signed case for us.
   395  	}
   396  	return r
   397  }
   398  
   399  // Similar to add, but computes the complement of the limit for bitsize b.
   400  func (l limit) com(b uint) limit {
   401  	switch b {
   402  	case 64:
   403  		return limit{
   404  			min:  ^l.max,
   405  			max:  ^l.min,
   406  			umin: ^l.umax,
   407  			umax: ^l.umin,
   408  		}
   409  	case 32:
   410  		return limit{
   411  			min:  int64(^int32(l.max)),
   412  			max:  int64(^int32(l.min)),
   413  			umin: uint64(^uint32(l.umax)),
   414  			umax: uint64(^uint32(l.umin)),
   415  		}
   416  	case 16:
   417  		return limit{
   418  			min:  int64(^int16(l.max)),
   419  			max:  int64(^int16(l.min)),
   420  			umin: uint64(^uint16(l.umax)),
   421  			umax: uint64(^uint16(l.umin)),
   422  		}
   423  	case 8:
   424  		return limit{
   425  			min:  int64(^int8(l.max)),
   426  			max:  int64(^int8(l.min)),
   427  			umin: uint64(^uint8(l.umax)),
   428  			umax: uint64(^uint8(l.umin)),
   429  		}
   430  	default:
   431  		panic("unreachable")
   432  	}
   433  }
   434  
   435  // Similar to add, but computes the negation of the limit for bitsize b.
   436  func (l limit) neg(b uint) limit {
   437  	return l.com(b).add(limit{min: 1, max: 1, umin: 1, umax: 1}, b)
   438  }
   439  
   440  // Similar to add, but computes the TrailingZeros of the limit for bitsize b.
   441  func (l limit) ctz(b uint) limit {
   442  	fixed, fixedCount := l.unsignedFixedLeadingBits()
   443  	if fixedCount == 64 {
   444  		constResult := min(uint(bits.TrailingZeros64(fixed)), b)
   445  		return limit{min: int64(constResult), max: int64(constResult), umin: uint64(constResult), umax: uint64(constResult)}
   446  	}
   447  
   448  	varying := 64 - fixedCount
   449  	if l.umin&((1<<varying)-1) != 0 {
   450  		// there will always be at least one non-zero bit in the varying part
   451  		varying--
   452  		return noLimit().unsignedMax(uint64(varying))
   453  	}
   454  	return noLimit().unsignedMax(uint64(min(uint(bits.TrailingZeros64(fixed)), b)))
   455  }
   456  
   457  // Similar to add, but computes the Len of the limit for bitsize b.
   458  func (l limit) bitlen(b uint) limit {
   459  	return noLimit().unsignedMinMax(
   460  		uint64(bits.Len64(l.umin)),
   461  		uint64(bits.Len64(l.umax)),
   462  	)
   463  }
   464  
   465  // Similar to add, but computes the PopCount of the limit for bitsize b.
   466  func (l limit) popcount(b uint) limit {
   467  	fixed, fixedCount := l.unsignedFixedLeadingBits()
   468  	varying := 64 - fixedCount
   469  	fixedContribution := uint64(bits.OnesCount64(fixed))
   470  
   471  	min := fixedContribution
   472  	max := fixedContribution + uint64(varying)
   473  
   474  	varyingMask := uint64(1)<<varying - 1
   475  
   476  	if varyingPartOfUmax := l.umax & varyingMask; uint(bits.OnesCount64(varyingPartOfUmax)) != varying {
   477  		// there is at least one zero bit in the varying part
   478  		max--
   479  	}
   480  	if varyingPartOfUmin := l.umin & varyingMask; varyingPartOfUmin != 0 {
   481  		// there is at least one non-zero bit in the varying part
   482  		min++
   483  	}
   484  
   485  	return noLimit().unsignedMinMax(min, max)
   486  }
   487  
   488  func (l limit) constValue() (_ int64, ok bool) {
   489  	switch {
   490  	case l.min == l.max:
   491  		return l.min, true
   492  	case l.umin == l.umax:
   493  		return int64(l.umin), true
   494  	default:
   495  		return 0, false
   496  	}
   497  }
   498  
   499  // a limitFact is a limit known for a particular value.
   500  type limitFact struct {
   501  	vid   ID
   502  	limit limit
   503  }
   504  
   505  // An ordering encodes facts like v < w.
   506  type ordering struct {
   507  	next *ordering // linked list of all known orderings for v.
   508  	// Note: v is implicit here, determined by which linked list it is in.
   509  	w *Value
   510  	d domain
   511  	r relation // one of ==,!=,<,<=,>,>=
   512  	// if d is boolean or pointer, r can only be ==, !=
   513  }
   514  
   515  // factsTable keeps track of relations between pairs of values.
   516  //
   517  // The fact table logic is sound, but incomplete. Outside of a few
   518  // special cases, it performs no deduction or arithmetic. While there
   519  // are known decision procedures for this, the ad hoc approach taken
   520  // by the facts table is effective for real code while remaining very
   521  // efficient.
   522  type factsTable struct {
   523  	// unsat is true if facts contains a contradiction.
   524  	//
   525  	// Note that the factsTable logic is incomplete, so if unsat
   526  	// is false, the assertions in factsTable could be satisfiable
   527  	// *or* unsatisfiable.
   528  	unsat      bool // true if facts contains a contradiction
   529  	unsatDepth int  // number of unsat checkpoints
   530  
   531  	// order* is a couple of partial order sets that record information
   532  	// about relations between SSA values in the signed and unsigned
   533  	// domain.
   534  	orderS *poset
   535  	orderU *poset
   536  
   537  	// orderings contains a list of known orderings between values.
   538  	// These lists are indexed by v.ID.
   539  	// We do not record transitive orderings. Only explicitly learned
   540  	// orderings are recorded. Transitive orderings can be obtained
   541  	// by walking along the individual orderings.
   542  	orderings map[ID]*ordering
   543  	// stack of IDs which have had an entry added in orderings.
   544  	// In addition, ID==0 are checkpoint markers.
   545  	orderingsStack []ID
   546  	orderingCache  *ordering // unused ordering records
   547  
   548  	// known lower and upper constant bounds on individual values.
   549  	limits       []limit     // indexed by value ID
   550  	limitStack   []limitFact // previous entries
   551  	recurseCheck []bool      // recursion detector for limit propagation
   552  
   553  	// For each slice s, a map from s to a len(s)/cap(s) value (if any)
   554  	// TODO: check if there are cases that matter where we have
   555  	// more than one len(s) for a slice. We could keep a list if necessary.
   556  	lens map[ID]*Value
   557  	caps map[ID]*Value
   558  
   559  	// reusedTopoSortIDsToBlockIndexes recycle allocations for topo-sort
   560  	reusedTopoSortIDsToBlockIndexes []uint
   561  }
   562  
   563  // checkpointBound is an invalid value used for checkpointing
   564  // and restoring factsTable.
   565  var checkpointBound = limitFact{}
   566  
   567  func newFactsTable(f *Func) *factsTable {
   568  	ft := &factsTable{}
   569  	ft.orderS = f.newPoset()
   570  	ft.orderU = f.newPoset()
   571  	ft.orderings = make(map[ID]*ordering)
   572  	ft.limits = f.Cache.allocLimitSlice(f.NumValues())
   573  	for _, b := range f.Blocks {
   574  		for _, v := range b.Values {
   575  			ft.limits[v.ID] = initLimit(v)
   576  		}
   577  	}
   578  	ft.limitStack = make([]limitFact, 4)
   579  	ft.recurseCheck = f.Cache.allocBoolSlice(f.NumValues())
   580  	return ft
   581  }
   582  
   583  // initLimitForNewValue initializes the limits for newly created values,
   584  // possibly needing to expand the limits slice. Currently used by
   585  // simplifyBlock when certain provably constant results are folded.
   586  func (ft *factsTable) initLimitForNewValue(v *Value) {
   587  	if int(v.ID) >= len(ft.limits) {
   588  		f := v.Block.Func
   589  		n := f.NumValues()
   590  		if cap(ft.limits) >= n {
   591  			ft.limits = ft.limits[:n]
   592  		} else {
   593  			old := ft.limits
   594  			ft.limits = f.Cache.allocLimitSlice(n)
   595  			copy(ft.limits, old)
   596  			f.Cache.freeLimitSlice(old)
   597  		}
   598  	}
   599  	ft.limits[v.ID] = initLimit(v)
   600  }
   601  
   602  // signedMin records the fact that we know v is at least
   603  // min in the signed domain.
   604  func (ft *factsTable) signedMin(v *Value, min int64) {
   605  	ft.newLimit(v, limit{min: min, max: math.MaxInt64, umin: 0, umax: math.MaxUint64})
   606  }
   607  
   608  // signedMax records the fact that we know v is at most
   609  // max in the signed domain.
   610  func (ft *factsTable) signedMax(v *Value, max int64) {
   611  	ft.newLimit(v, limit{min: math.MinInt64, max: max, umin: 0, umax: math.MaxUint64})
   612  }
   613  func (ft *factsTable) signedMinMax(v *Value, min, max int64) {
   614  	ft.newLimit(v, limit{min: min, max: max, umin: 0, umax: math.MaxUint64})
   615  }
   616  
   617  // setNonNegative records the fact that v is known to be non-negative.
   618  func (ft *factsTable) setNonNegative(v *Value) {
   619  	ft.signedMin(v, 0)
   620  }
   621  
   622  // unsignedMin records the fact that we know v is at least
   623  // min in the unsigned domain.
   624  func (ft *factsTable) unsignedMin(v *Value, min uint64) {
   625  	ft.newLimit(v, limit{min: math.MinInt64, max: math.MaxInt64, umin: min, umax: math.MaxUint64})
   626  }
   627  
   628  // unsignedMax records the fact that we know v is at most
   629  // max in the unsigned domain.
   630  func (ft *factsTable) unsignedMax(v *Value, max uint64) {
   631  	ft.newLimit(v, limit{min: math.MinInt64, max: math.MaxInt64, umin: 0, umax: max})
   632  }
   633  func (ft *factsTable) unsignedMinMax(v *Value, min, max uint64) {
   634  	ft.newLimit(v, limit{min: math.MinInt64, max: math.MaxInt64, umin: min, umax: max})
   635  }
   636  
   637  func (ft *factsTable) booleanFalse(v *Value) {
   638  	ft.newLimit(v, limit{min: 0, max: 0, umin: 0, umax: 0})
   639  }
   640  func (ft *factsTable) booleanTrue(v *Value) {
   641  	ft.newLimit(v, limit{min: 1, max: 1, umin: 1, umax: 1})
   642  }
   643  func (ft *factsTable) pointerNil(v *Value) {
   644  	ft.newLimit(v, limit{min: 0, max: 0, umin: 0, umax: 0})
   645  }
   646  func (ft *factsTable) pointerNonNil(v *Value) {
   647  	l := noLimit()
   648  	l.umin = 1
   649  	ft.newLimit(v, l)
   650  }
   651  
   652  // newLimit adds new limiting information for v.
   653  func (ft *factsTable) newLimit(v *Value, newLim limit) {
   654  	oldLim := ft.limits[v.ID]
   655  
   656  	// Merge old and new information.
   657  	lim := oldLim.intersect(newLim)
   658  
   659  	// signed <-> unsigned propagation
   660  	if lim.min >= 0 {
   661  		lim = lim.unsignedMinMax(uint64(lim.min), uint64(lim.max))
   662  	}
   663  	if fitsInBitsU(lim.umax, uint(8*v.Type.Size()-1)) {
   664  		lim = lim.signedMinMax(int64(lim.umin), int64(lim.umax))
   665  	}
   666  
   667  	if lim == oldLim {
   668  		return // nothing new to record
   669  	}
   670  
   671  	if lim.unsat() {
   672  		ft.unsat = true
   673  		return
   674  	}
   675  
   676  	// Check for recursion. This normally happens because in unsatisfiable
   677  	// cases we have a < b < a, and every update to a's limits returns
   678  	// here again with the limit increased by 2.
   679  	// Normally this is caught early by the orderS/orderU posets, but in
   680  	// cases where the comparisons jump between signed and unsigned domains,
   681  	// the posets will not notice.
   682  	if ft.recurseCheck[v.ID] {
   683  		// This should only happen for unsatisfiable cases. TODO: check
   684  		return
   685  	}
   686  	ft.recurseCheck[v.ID] = true
   687  	defer func() {
   688  		ft.recurseCheck[v.ID] = false
   689  	}()
   690  
   691  	// Record undo information.
   692  	ft.limitStack = append(ft.limitStack, limitFact{v.ID, oldLim})
   693  	// Record new information.
   694  	ft.limits[v.ID] = lim
   695  	if v.Block.Func.pass.debug > 2 {
   696  		// TODO: pos is probably wrong. This is the position where v is defined,
   697  		// not the position where we learned the fact about it (which was
   698  		// probably some subsequent compare+branch).
   699  		v.Block.Func.Warnl(v.Pos, "new limit %s %s unsat=%v", v, lim.String(), ft.unsat)
   700  	}
   701  
   702  	// Propagate this new constant range to other values
   703  	// that we know are ordered with respect to this one.
   704  	// Note overflow/underflow in the arithmetic below is ok,
   705  	// it will just lead to imprecision (undetected unsatisfiability).
   706  	for o := ft.orderings[v.ID]; o != nil; o = o.next {
   707  		switch o.d {
   708  		case signed:
   709  			switch o.r {
   710  			case eq: // v == w
   711  				ft.signedMinMax(o.w, lim.min, lim.max)
   712  			case lt | eq: // v <= w
   713  				ft.signedMin(o.w, lim.min)
   714  			case lt: // v < w
   715  				ft.signedMin(o.w, lim.min+1)
   716  			case gt | eq: // v >= w
   717  				ft.signedMax(o.w, lim.max)
   718  			case gt: // v > w
   719  				ft.signedMax(o.w, lim.max-1)
   720  			case lt | gt: // v != w
   721  				if lim.min == lim.max { // v is a constant
   722  					c := lim.min
   723  					if ft.limits[o.w.ID].min == c {
   724  						ft.signedMin(o.w, c+1)
   725  					}
   726  					if ft.limits[o.w.ID].max == c {
   727  						ft.signedMax(o.w, c-1)
   728  					}
   729  				}
   730  			}
   731  		case unsigned:
   732  			switch o.r {
   733  			case eq: // v == w
   734  				ft.unsignedMinMax(o.w, lim.umin, lim.umax)
   735  			case lt | eq: // v <= w
   736  				ft.unsignedMin(o.w, lim.umin)
   737  			case lt: // v < w
   738  				ft.unsignedMin(o.w, lim.umin+1)
   739  			case gt | eq: // v >= w
   740  				ft.unsignedMax(o.w, lim.umax)
   741  			case gt: // v > w
   742  				ft.unsignedMax(o.w, lim.umax-1)
   743  			case lt | gt: // v != w
   744  				if lim.umin == lim.umax { // v is a constant
   745  					c := lim.umin
   746  					if ft.limits[o.w.ID].umin == c {
   747  						ft.unsignedMin(o.w, c+1)
   748  					}
   749  					if ft.limits[o.w.ID].umax == c {
   750  						ft.unsignedMax(o.w, c-1)
   751  					}
   752  				}
   753  			}
   754  		case boolean:
   755  			switch o.r {
   756  			case eq:
   757  				if lim.min == 0 && lim.max == 0 { // constant false
   758  					ft.booleanFalse(o.w)
   759  				}
   760  				if lim.min == 1 && lim.max == 1 { // constant true
   761  					ft.booleanTrue(o.w)
   762  				}
   763  			case lt | gt:
   764  				if lim.min == 0 && lim.max == 0 { // constant false
   765  					ft.booleanTrue(o.w)
   766  				}
   767  				if lim.min == 1 && lim.max == 1 { // constant true
   768  					ft.booleanFalse(o.w)
   769  				}
   770  			}
   771  		case pointer:
   772  			switch o.r {
   773  			case eq:
   774  				if lim.umax == 0 { // nil
   775  					ft.pointerNil(o.w)
   776  				}
   777  				if lim.umin > 0 { // non-nil
   778  					ft.pointerNonNil(o.w)
   779  				}
   780  			case lt | gt:
   781  				if lim.umax == 0 { // nil
   782  					ft.pointerNonNil(o.w)
   783  				}
   784  				// note: not equal to non-nil doesn't tell us anything.
   785  			}
   786  		}
   787  	}
   788  
   789  	// If this is new known constant for a boolean value,
   790  	// extract relation between its args. For example, if
   791  	// We learn v is false, and v is defined as a<b, then we learn a>=b.
   792  	if v.Type.IsBoolean() {
   793  		// If we reach here, it is because we have a more restrictive
   794  		// value for v than the default. The only two such values
   795  		// are constant true or constant false.
   796  		if lim.min != lim.max {
   797  			v.Block.Func.Fatalf("boolean not constant %v", v)
   798  		}
   799  		isTrue := lim.min == 1
   800  		if dr, ok := domainRelationTable[v.Op]; ok && v.Op != OpIsInBounds && v.Op != OpIsSliceInBounds {
   801  			d := dr.d
   802  			r := dr.r
   803  			if d == signed && ft.isNonNegative(v.Args[0]) && ft.isNonNegative(v.Args[1]) {
   804  				d |= unsigned
   805  			}
   806  			if !isTrue {
   807  				r ^= lt | gt | eq
   808  			}
   809  			// TODO: v.Block is wrong?
   810  			addRestrictions(v.Block, ft, d, v.Args[0], v.Args[1], r)
   811  		}
   812  		switch v.Op {
   813  		case OpIsNonNil:
   814  			if isTrue {
   815  				ft.pointerNonNil(v.Args[0])
   816  			} else {
   817  				ft.pointerNil(v.Args[0])
   818  			}
   819  		case OpIsInBounds, OpIsSliceInBounds:
   820  			// 0 <= a0 < a1 (or 0 <= a0 <= a1)
   821  			r := lt
   822  			if v.Op == OpIsSliceInBounds {
   823  				r |= eq
   824  			}
   825  			if isTrue {
   826  				// On the positive branch, we learn:
   827  				//   signed: 0 <= a0 < a1 (or 0 <= a0 <= a1)
   828  				//   unsigned:    a0 < a1 (or a0 <= a1)
   829  				ft.setNonNegative(v.Args[0])
   830  				ft.update(v.Block, v.Args[0], v.Args[1], signed, r)
   831  				ft.update(v.Block, v.Args[0], v.Args[1], unsigned, r)
   832  			} else {
   833  				// On the negative branch, we learn (0 > a0 ||
   834  				// a0 >= a1). In the unsigned domain, this is
   835  				// simply a0 >= a1 (which is the reverse of the
   836  				// positive branch, so nothing surprising).
   837  				// But in the signed domain, we can't express the ||
   838  				// condition, so check if a0 is non-negative instead,
   839  				// to be able to learn something.
   840  				r ^= lt | gt | eq // >= (index) or > (slice)
   841  				if ft.isNonNegative(v.Args[0]) {
   842  					ft.update(v.Block, v.Args[0], v.Args[1], signed, r)
   843  				}
   844  				ft.update(v.Block, v.Args[0], v.Args[1], unsigned, r)
   845  				// TODO: v.Block is wrong here
   846  			}
   847  		}
   848  	}
   849  }
   850  
   851  func (ft *factsTable) addOrdering(v, w *Value, d domain, r relation) {
   852  	o := ft.orderingCache
   853  	if o == nil {
   854  		o = &ordering{}
   855  	} else {
   856  		ft.orderingCache = o.next
   857  	}
   858  	o.w = w
   859  	o.d = d
   860  	o.r = r
   861  	o.next = ft.orderings[v.ID]
   862  	ft.orderings[v.ID] = o
   863  	ft.orderingsStack = append(ft.orderingsStack, v.ID)
   864  }
   865  
   866  // update updates the set of relations between v and w in domain d
   867  // restricting it to r.
   868  func (ft *factsTable) update(parent *Block, v, w *Value, d domain, r relation) {
   869  	if parent.Func.pass.debug > 2 {
   870  		parent.Func.Warnl(parent.Pos, "parent=%s, update %s %s %s", parent, v, w, r)
   871  	}
   872  	// No need to do anything else if we already found unsat.
   873  	if ft.unsat {
   874  		return
   875  	}
   876  
   877  	// Self-fact. It's wasteful to register it into the facts
   878  	// table, so just note whether it's satisfiable
   879  	if v == w {
   880  		if r&eq == 0 {
   881  			ft.unsat = true
   882  		}
   883  		return
   884  	}
   885  
   886  	if d == signed || d == unsigned {
   887  		var ok bool
   888  		order := ft.orderS
   889  		if d == unsigned {
   890  			order = ft.orderU
   891  		}
   892  		switch r {
   893  		case lt:
   894  			ok = order.SetOrder(v, w)
   895  		case gt:
   896  			ok = order.SetOrder(w, v)
   897  		case lt | eq:
   898  			ok = order.SetOrderOrEqual(v, w)
   899  		case gt | eq:
   900  			ok = order.SetOrderOrEqual(w, v)
   901  		case eq:
   902  			ok = order.SetEqual(v, w)
   903  		case lt | gt:
   904  			ok = order.SetNonEqual(v, w)
   905  		default:
   906  			panic("unknown relation")
   907  		}
   908  		ft.addOrdering(v, w, d, r)
   909  		ft.addOrdering(w, v, d, reverseBits[r])
   910  
   911  		if !ok {
   912  			if parent.Func.pass.debug > 2 {
   913  				parent.Func.Warnl(parent.Pos, "unsat %s %s %s", v, w, r)
   914  			}
   915  			ft.unsat = true
   916  			return
   917  		}
   918  	}
   919  	if d == boolean || d == pointer {
   920  		for o := ft.orderings[v.ID]; o != nil; o = o.next {
   921  			if o.d == d && o.w == w {
   922  				// We already know a relationship between v and w.
   923  				// Either it is a duplicate, or it is a contradiction,
   924  				// as we only allow eq and lt|gt for these domains,
   925  				if o.r != r {
   926  					ft.unsat = true
   927  				}
   928  				return
   929  			}
   930  		}
   931  		// TODO: this does not do transitive equality.
   932  		// We could use a poset like above, but somewhat degenerate (==,!= only).
   933  		ft.addOrdering(v, w, d, r)
   934  		ft.addOrdering(w, v, d, r) // note: reverseBits unnecessary for eq and lt|gt.
   935  	}
   936  
   937  	// Extract new constant limits based on the comparison.
   938  	vLimit := ft.limits[v.ID]
   939  	wLimit := ft.limits[w.ID]
   940  	// Note: all the +1/-1 below could overflow/underflow. Either will
   941  	// still generate correct results, it will just lead to imprecision.
   942  	// In fact if there is overflow/underflow, the corresponding
   943  	// code is unreachable because the known range is outside the range
   944  	// of the value's type.
   945  	switch d {
   946  	case signed:
   947  		switch r {
   948  		case eq: // v == w
   949  			ft.signedMinMax(v, wLimit.min, wLimit.max)
   950  			ft.signedMinMax(w, vLimit.min, vLimit.max)
   951  		case lt: // v < w
   952  			ft.signedMax(v, wLimit.max-1)
   953  			ft.signedMin(w, vLimit.min+1)
   954  		case lt | eq: // v <= w
   955  			ft.signedMax(v, wLimit.max)
   956  			ft.signedMin(w, vLimit.min)
   957  		case gt: // v > w
   958  			ft.signedMin(v, wLimit.min+1)
   959  			ft.signedMax(w, vLimit.max-1)
   960  		case gt | eq: // v >= w
   961  			ft.signedMin(v, wLimit.min)
   962  			ft.signedMax(w, vLimit.max)
   963  		case lt | gt: // v != w
   964  			if vLimit.min == vLimit.max { // v is a constant
   965  				c := vLimit.min
   966  				if wLimit.min == c {
   967  					ft.signedMin(w, c+1)
   968  				}
   969  				if wLimit.max == c {
   970  					ft.signedMax(w, c-1)
   971  				}
   972  			}
   973  			if wLimit.min == wLimit.max { // w is a constant
   974  				c := wLimit.min
   975  				if vLimit.min == c {
   976  					ft.signedMin(v, c+1)
   977  				}
   978  				if vLimit.max == c {
   979  					ft.signedMax(v, c-1)
   980  				}
   981  			}
   982  		}
   983  	case unsigned:
   984  		switch r {
   985  		case eq: // v == w
   986  			ft.unsignedMinMax(v, wLimit.umin, wLimit.umax)
   987  			ft.unsignedMinMax(w, vLimit.umin, vLimit.umax)
   988  		case lt: // v < w
   989  			ft.unsignedMax(v, wLimit.umax-1)
   990  			ft.unsignedMin(w, vLimit.umin+1)
   991  		case lt | eq: // v <= w
   992  			ft.unsignedMax(v, wLimit.umax)
   993  			ft.unsignedMin(w, vLimit.umin)
   994  		case gt: // v > w
   995  			ft.unsignedMin(v, wLimit.umin+1)
   996  			ft.unsignedMax(w, vLimit.umax-1)
   997  		case gt | eq: // v >= w
   998  			ft.unsignedMin(v, wLimit.umin)
   999  			ft.unsignedMax(w, vLimit.umax)
  1000  		case lt | gt: // v != w
  1001  			if vLimit.umin == vLimit.umax { // v is a constant
  1002  				c := vLimit.umin
  1003  				if wLimit.umin == c {
  1004  					ft.unsignedMin(w, c+1)
  1005  				}
  1006  				if wLimit.umax == c {
  1007  					ft.unsignedMax(w, c-1)
  1008  				}
  1009  			}
  1010  			if wLimit.umin == wLimit.umax { // w is a constant
  1011  				c := wLimit.umin
  1012  				if vLimit.umin == c {
  1013  					ft.unsignedMin(v, c+1)
  1014  				}
  1015  				if vLimit.umax == c {
  1016  					ft.unsignedMax(v, c-1)
  1017  				}
  1018  			}
  1019  		}
  1020  	case boolean:
  1021  		switch r {
  1022  		case eq: // v == w
  1023  			if vLimit.min == 1 { // v is true
  1024  				ft.booleanTrue(w)
  1025  			}
  1026  			if vLimit.max == 0 { // v is false
  1027  				ft.booleanFalse(w)
  1028  			}
  1029  			if wLimit.min == 1 { // w is true
  1030  				ft.booleanTrue(v)
  1031  			}
  1032  			if wLimit.max == 0 { // w is false
  1033  				ft.booleanFalse(v)
  1034  			}
  1035  		case lt | gt: // v != w
  1036  			if vLimit.min == 1 { // v is true
  1037  				ft.booleanFalse(w)
  1038  			}
  1039  			if vLimit.max == 0 { // v is false
  1040  				ft.booleanTrue(w)
  1041  			}
  1042  			if wLimit.min == 1 { // w is true
  1043  				ft.booleanFalse(v)
  1044  			}
  1045  			if wLimit.max == 0 { // w is false
  1046  				ft.booleanTrue(v)
  1047  			}
  1048  		}
  1049  	case pointer:
  1050  		switch r {
  1051  		case eq: // v == w
  1052  			if vLimit.umax == 0 { // v is nil
  1053  				ft.pointerNil(w)
  1054  			}
  1055  			if vLimit.umin > 0 { // v is non-nil
  1056  				ft.pointerNonNil(w)
  1057  			}
  1058  			if wLimit.umax == 0 { // w is nil
  1059  				ft.pointerNil(v)
  1060  			}
  1061  			if wLimit.umin > 0 { // w is non-nil
  1062  				ft.pointerNonNil(v)
  1063  			}
  1064  		case lt | gt: // v != w
  1065  			if vLimit.umax == 0 { // v is nil
  1066  				ft.pointerNonNil(w)
  1067  			}
  1068  			if wLimit.umax == 0 { // w is nil
  1069  				ft.pointerNonNil(v)
  1070  			}
  1071  			// Note: the other direction doesn't work.
  1072  			// Being not equal to a non-nil pointer doesn't
  1073  			// make you (necessarily) a nil pointer.
  1074  		}
  1075  	}
  1076  
  1077  	// Derived facts below here are only about numbers.
  1078  	if d != signed && d != unsigned {
  1079  		return
  1080  	}
  1081  
  1082  	// Additional facts we know given the relationship between len and cap.
  1083  	//
  1084  	// TODO: Since prove now derives transitive relations, it
  1085  	// should be sufficient to learn that len(w) <= cap(w) at the
  1086  	// beginning of prove where we look for all len/cap ops.
  1087  	if v.Op == OpSliceLen && r&lt == 0 && ft.caps[v.Args[0].ID] != nil {
  1088  		// len(s) > w implies cap(s) > w
  1089  		// len(s) >= w implies cap(s) >= w
  1090  		// len(s) == w implies cap(s) >= w
  1091  		ft.update(parent, ft.caps[v.Args[0].ID], w, d, r|gt)
  1092  	}
  1093  	if w.Op == OpSliceLen && r&gt == 0 && ft.caps[w.Args[0].ID] != nil {
  1094  		// same, length on the RHS.
  1095  		ft.update(parent, v, ft.caps[w.Args[0].ID], d, r|lt)
  1096  	}
  1097  	if v.Op == OpSliceCap && r&gt == 0 && ft.lens[v.Args[0].ID] != nil {
  1098  		// cap(s) < w implies len(s) < w
  1099  		// cap(s) <= w implies len(s) <= w
  1100  		// cap(s) == w implies len(s) <= w
  1101  		ft.update(parent, ft.lens[v.Args[0].ID], w, d, r|lt)
  1102  	}
  1103  	if w.Op == OpSliceCap && r&lt == 0 && ft.lens[w.Args[0].ID] != nil {
  1104  		// same, capacity on the RHS.
  1105  		ft.update(parent, v, ft.lens[w.Args[0].ID], d, r|gt)
  1106  	}
  1107  
  1108  	// Process fence-post implications.
  1109  	//
  1110  	// First, make the condition > or >=.
  1111  	if r == lt || r == lt|eq {
  1112  		v, w = w, v
  1113  		r = reverseBits[r]
  1114  	}
  1115  	switch r {
  1116  	case gt:
  1117  		if x, delta := isConstDelta(v); x != nil && delta == 1 {
  1118  			// x+1 > w  ⇒  x >= w
  1119  			//
  1120  			// This is useful for eliminating the
  1121  			// growslice branch of append.
  1122  			ft.update(parent, x, w, d, gt|eq)
  1123  		} else if x, delta := isConstDelta(w); x != nil && delta == -1 {
  1124  			// v > x-1  ⇒  v >= x
  1125  			ft.update(parent, v, x, d, gt|eq)
  1126  		}
  1127  	case gt | eq:
  1128  		if x, delta := isConstDelta(v); x != nil && delta == -1 {
  1129  			// x-1 >= w && x > min  ⇒  x > w
  1130  			//
  1131  			// Useful for i > 0; s[i-1].
  1132  			lim := ft.limits[x.ID]
  1133  			if (d == signed && lim.min > opMin[v.Op]) || (d == unsigned && lim.umin > 0) {
  1134  				ft.update(parent, x, w, d, gt)
  1135  			}
  1136  		} else if x, delta := isConstDelta(w); x != nil && delta == 1 {
  1137  			// v >= x+1 && x < max  ⇒  v > x
  1138  			lim := ft.limits[x.ID]
  1139  			if (d == signed && lim.max < opMax[w.Op]) || (d == unsigned && lim.umax < opUMax[w.Op]) {
  1140  				ft.update(parent, v, x, d, gt)
  1141  			}
  1142  		}
  1143  	}
  1144  
  1145  	// Process: x+delta > w (with delta constant)
  1146  	// Only signed domain for now (useful for accesses to slices in loops).
  1147  	if r == gt || r == gt|eq {
  1148  		if x, delta := isConstDelta(v); x != nil && d == signed {
  1149  			if parent.Func.pass.debug > 1 {
  1150  				parent.Func.Warnl(parent.Pos, "x+d %s w; x:%v %v delta:%v w:%v d:%v", r, x, parent.String(), delta, w.AuxInt, d)
  1151  			}
  1152  			underflow := true
  1153  			if delta < 0 {
  1154  				l := ft.limits[x.ID]
  1155  				if (x.Type.Size() == 8 && l.min >= math.MinInt64-delta) ||
  1156  					(x.Type.Size() == 4 && l.min >= math.MinInt32-delta) {
  1157  					underflow = false
  1158  				}
  1159  			}
  1160  			if delta < 0 && !underflow {
  1161  				// If delta < 0 and x+delta cannot underflow then x > x+delta (that is, x > v)
  1162  				ft.update(parent, x, v, signed, gt)
  1163  			}
  1164  			if !w.isGenericIntConst() {
  1165  				// If we know that x+delta > w but w is not constant, we can derive:
  1166  				//    if delta < 0 and x+delta cannot underflow, then x > w
  1167  				// This is useful for loops with bounds "len(slice)-K" (delta = -K)
  1168  				if delta < 0 && !underflow {
  1169  					ft.update(parent, x, w, signed, r)
  1170  				}
  1171  			} else {
  1172  				// With w,delta constants, we want to derive: x+delta > w  ⇒  x > w-delta
  1173  				//
  1174  				// We compute (using integers of the correct size):
  1175  				//    min = w - delta
  1176  				//    max = MaxInt - delta
  1177  				//
  1178  				// And we prove that:
  1179  				//    if min<max: min < x AND x <= max
  1180  				//    if min>max: min < x OR  x <= max
  1181  				//
  1182  				// This is always correct, even in case of overflow.
  1183  				//
  1184  				// If the initial fact is x+delta >= w instead, the derived conditions are:
  1185  				//    if min<max: min <= x AND x <= max
  1186  				//    if min>max: min <= x OR  x <= max
  1187  				//
  1188  				// Notice the conditions for max are still <=, as they handle overflows.
  1189  				var min, max int64
  1190  				switch x.Type.Size() {
  1191  				case 8:
  1192  					min = w.AuxInt - delta
  1193  					max = int64(^uint64(0)>>1) - delta
  1194  				case 4:
  1195  					min = int64(int32(w.AuxInt) - int32(delta))
  1196  					max = int64(int32(^uint32(0)>>1) - int32(delta))
  1197  				case 2:
  1198  					min = int64(int16(w.AuxInt) - int16(delta))
  1199  					max = int64(int16(^uint16(0)>>1) - int16(delta))
  1200  				case 1:
  1201  					min = int64(int8(w.AuxInt) - int8(delta))
  1202  					max = int64(int8(^uint8(0)>>1) - int8(delta))
  1203  				default:
  1204  					panic("unimplemented")
  1205  				}
  1206  
  1207  				if min < max {
  1208  					// Record that x > min and max >= x
  1209  					if r == gt {
  1210  						min++
  1211  					}
  1212  					ft.signedMinMax(x, min, max)
  1213  				} else {
  1214  					// We know that either x>min OR x<=max. factsTable cannot record OR conditions,
  1215  					// so let's see if we can already prove that one of them is false, in which case
  1216  					// the other must be true
  1217  					l := ft.limits[x.ID]
  1218  					if l.max <= min {
  1219  						if r&eq == 0 || l.max < min {
  1220  							// x>min (x>=min) is impossible, so it must be x<=max
  1221  							ft.signedMax(x, max)
  1222  						}
  1223  					} else if l.min > max {
  1224  						// x<=max is impossible, so it must be x>min
  1225  						if r == gt {
  1226  							min++
  1227  						}
  1228  						ft.signedMin(x, min)
  1229  					}
  1230  				}
  1231  			}
  1232  		}
  1233  	}
  1234  
  1235  	// Look through value-preserving extensions.
  1236  	// If the domain is appropriate for the pre-extension Type,
  1237  	// repeat the update with the pre-extension Value.
  1238  	if isCleanExt(v) {
  1239  		switch {
  1240  		case d == signed && v.Args[0].Type.IsSigned():
  1241  			fallthrough
  1242  		case d == unsigned && !v.Args[0].Type.IsSigned():
  1243  			ft.update(parent, v.Args[0], w, d, r)
  1244  		}
  1245  	}
  1246  	if isCleanExt(w) {
  1247  		switch {
  1248  		case d == signed && w.Args[0].Type.IsSigned():
  1249  			fallthrough
  1250  		case d == unsigned && !w.Args[0].Type.IsSigned():
  1251  			ft.update(parent, v, w.Args[0], d, r)
  1252  		}
  1253  	}
  1254  }
  1255  
  1256  var opMin = map[Op]int64{
  1257  	OpAdd64: math.MinInt64, OpSub64: math.MinInt64,
  1258  	OpAdd32: math.MinInt32, OpSub32: math.MinInt32,
  1259  }
  1260  
  1261  var opMax = map[Op]int64{
  1262  	OpAdd64: math.MaxInt64, OpSub64: math.MaxInt64,
  1263  	OpAdd32: math.MaxInt32, OpSub32: math.MaxInt32,
  1264  }
  1265  
  1266  var opUMax = map[Op]uint64{
  1267  	OpAdd64: math.MaxUint64, OpSub64: math.MaxUint64,
  1268  	OpAdd32: math.MaxUint32, OpSub32: math.MaxUint32,
  1269  }
  1270  
  1271  // isNonNegative reports whether v is known to be non-negative.
  1272  func (ft *factsTable) isNonNegative(v *Value) bool {
  1273  	return ft.limits[v.ID].min >= 0
  1274  }
  1275  
  1276  // checkpoint saves the current state of known relations.
  1277  // Called when descending on a branch.
  1278  func (ft *factsTable) checkpoint() {
  1279  	if ft.unsat {
  1280  		ft.unsatDepth++
  1281  	}
  1282  	ft.limitStack = append(ft.limitStack, checkpointBound)
  1283  	ft.orderS.Checkpoint()
  1284  	ft.orderU.Checkpoint()
  1285  	ft.orderingsStack = append(ft.orderingsStack, 0)
  1286  }
  1287  
  1288  // restore restores known relation to the state just
  1289  // before the previous checkpoint.
  1290  // Called when backing up on a branch.
  1291  func (ft *factsTable) restore() {
  1292  	if ft.unsatDepth > 0 {
  1293  		ft.unsatDepth--
  1294  	} else {
  1295  		ft.unsat = false
  1296  	}
  1297  	for {
  1298  		old := ft.limitStack[len(ft.limitStack)-1]
  1299  		ft.limitStack = ft.limitStack[:len(ft.limitStack)-1]
  1300  		if old.vid == 0 { // checkpointBound
  1301  			break
  1302  		}
  1303  		ft.limits[old.vid] = old.limit
  1304  	}
  1305  	ft.orderS.Undo()
  1306  	ft.orderU.Undo()
  1307  	for {
  1308  		id := ft.orderingsStack[len(ft.orderingsStack)-1]
  1309  		ft.orderingsStack = ft.orderingsStack[:len(ft.orderingsStack)-1]
  1310  		if id == 0 { // checkpoint marker
  1311  			break
  1312  		}
  1313  		o := ft.orderings[id]
  1314  		ft.orderings[id] = o.next
  1315  		o.next = ft.orderingCache
  1316  		ft.orderingCache = o
  1317  	}
  1318  }
  1319  
  1320  var (
  1321  	reverseBits = [...]relation{0, 4, 2, 6, 1, 5, 3, 7}
  1322  
  1323  	// maps what we learn when the positive branch is taken.
  1324  	// For example:
  1325  	//      OpLess8:   {signed, lt},
  1326  	//	v1 = (OpLess8 v2 v3).
  1327  	// If we learn that v1 is true, then we can deduce that v2<v3
  1328  	// in the signed domain.
  1329  	domainRelationTable = map[Op]struct {
  1330  		d domain
  1331  		r relation
  1332  	}{
  1333  		OpEq8:   {signed | unsigned, eq},
  1334  		OpEq16:  {signed | unsigned, eq},
  1335  		OpEq32:  {signed | unsigned, eq},
  1336  		OpEq64:  {signed | unsigned, eq},
  1337  		OpEqPtr: {pointer, eq},
  1338  		OpEqB:   {boolean, eq},
  1339  
  1340  		OpNeq8:   {signed | unsigned, lt | gt},
  1341  		OpNeq16:  {signed | unsigned, lt | gt},
  1342  		OpNeq32:  {signed | unsigned, lt | gt},
  1343  		OpNeq64:  {signed | unsigned, lt | gt},
  1344  		OpNeqPtr: {pointer, lt | gt},
  1345  		OpNeqB:   {boolean, lt | gt},
  1346  
  1347  		OpLess8:   {signed, lt},
  1348  		OpLess8U:  {unsigned, lt},
  1349  		OpLess16:  {signed, lt},
  1350  		OpLess16U: {unsigned, lt},
  1351  		OpLess32:  {signed, lt},
  1352  		OpLess32U: {unsigned, lt},
  1353  		OpLess64:  {signed, lt},
  1354  		OpLess64U: {unsigned, lt},
  1355  
  1356  		OpLeq8:   {signed, lt | eq},
  1357  		OpLeq8U:  {unsigned, lt | eq},
  1358  		OpLeq16:  {signed, lt | eq},
  1359  		OpLeq16U: {unsigned, lt | eq},
  1360  		OpLeq32:  {signed, lt | eq},
  1361  		OpLeq32U: {unsigned, lt | eq},
  1362  		OpLeq64:  {signed, lt | eq},
  1363  		OpLeq64U: {unsigned, lt | eq},
  1364  	}
  1365  )
  1366  
  1367  // cleanup returns the posets to the free list
  1368  func (ft *factsTable) cleanup(f *Func) {
  1369  	for _, po := range []*poset{ft.orderS, ft.orderU} {
  1370  		// Make sure it's empty as it should be. A non-empty poset
  1371  		// might cause errors and miscompilations if reused.
  1372  		if checkEnabled {
  1373  			if err := po.CheckEmpty(); err != nil {
  1374  				f.Fatalf("poset not empty after function %s: %v", f.Name, err)
  1375  			}
  1376  		}
  1377  		f.retPoset(po)
  1378  	}
  1379  	f.Cache.freeLimitSlice(ft.limits)
  1380  	f.Cache.freeBoolSlice(ft.recurseCheck)
  1381  	if cap(ft.reusedTopoSortIDsToBlockIndexes) > 0 {
  1382  		f.Cache.freeUintSlice(ft.reusedTopoSortIDsToBlockIndexes)
  1383  	}
  1384  }
  1385  
  1386  // addSlicesOfSameLen finds the slices that are in the same block and whose Op
  1387  // is OpPhi and always have the same length, then add the equality relationship
  1388  // between them to ft. If two slices start out with the same length and decrease
  1389  // in length by the same amount on each round of the loop (or in the if block),
  1390  // then we think their lengths are always equal.
  1391  //
  1392  // See https://go.dev/issues/75144
  1393  //
  1394  // In fact, we are just propagating the equality
  1395  //
  1396  //	if len(a) == len(b) { // from here
  1397  //		for len(a) > 4 {
  1398  //			a = a[4:]
  1399  //			b = b[4:]
  1400  //		}
  1401  //		if len(a) == len(b) { // to here
  1402  //			return true
  1403  //		}
  1404  //	}
  1405  //
  1406  // or change the for to if:
  1407  //
  1408  //	if len(a) == len(b) { // from here
  1409  //		if len(a) > 4 {
  1410  //			a = a[4:]
  1411  //			b = b[4:]
  1412  //		}
  1413  //		if len(a) == len(b) { // to here
  1414  //			return true
  1415  //		}
  1416  //	}
  1417  func addSlicesOfSameLen(ft *factsTable, b *Block) {
  1418  	// Let w points to the first value we're interested in, and then we
  1419  	// only process those values ​​that appear to be the same length as w,
  1420  	// looping only once. This should be enough in most cases. And u is
  1421  	// similar to w, see comment for predIndex.
  1422  	var u, w *Value
  1423  	var i, j, k sliceInfo
  1424  	isInterested := func(v *Value) bool {
  1425  		j = getSliceInfo(v)
  1426  		return j.sliceWhere != sliceUnknown
  1427  	}
  1428  	for _, v := range b.Values {
  1429  		if v.Uses == 0 {
  1430  			continue
  1431  		}
  1432  		if v.Op == OpPhi && len(v.Args) == 2 && ft.lens[v.ID] != nil && isInterested(v) {
  1433  			if j.predIndex == 1 && ft.lens[v.Args[0].ID] != nil {
  1434  				// found v = (Phi x (SliceMake _ (Add64 (Const64 [n]) (SliceLen x)) _))) or
  1435  				// v = (Phi x (SliceMake _ (Add64 (Const64 [n]) (SliceLen v)) _)))
  1436  				if w == nil {
  1437  					k = j
  1438  					w = v
  1439  					continue
  1440  				}
  1441  				// propagate the equality
  1442  				if j == k && ft.orderS.Equal(ft.lens[v.Args[0].ID], ft.lens[w.Args[0].ID]) {
  1443  					ft.update(b, ft.lens[v.ID], ft.lens[w.ID], signed, eq)
  1444  				}
  1445  			} else if j.predIndex == 0 && ft.lens[v.Args[1].ID] != nil {
  1446  				// found v = (Phi (SliceMake _ (Add64 (Const64 [n]) (SliceLen x)) _)) x) or
  1447  				// v = (Phi (SliceMake _ (Add64 (Const64 [n]) (SliceLen v)) _)) x)
  1448  				if u == nil {
  1449  					i = j
  1450  					u = v
  1451  					continue
  1452  				}
  1453  				// propagate the equality
  1454  				if j == i && ft.orderS.Equal(ft.lens[v.Args[1].ID], ft.lens[u.Args[1].ID]) {
  1455  					ft.update(b, ft.lens[v.ID], ft.lens[u.ID], signed, eq)
  1456  				}
  1457  			}
  1458  		}
  1459  	}
  1460  }
  1461  
  1462  type sliceWhere int
  1463  
  1464  const (
  1465  	sliceUnknown sliceWhere = iota
  1466  	sliceInFor
  1467  	sliceInIf
  1468  )
  1469  
  1470  // predIndex is used to indicate the branch represented by the predecessor
  1471  // block in which the slicing operation occurs.
  1472  type predIndex int
  1473  
  1474  type sliceInfo struct {
  1475  	lengthDiff int64
  1476  	sliceWhere
  1477  	predIndex
  1478  }
  1479  
  1480  // getSliceInfo returns the negative increment of the slice length in a slice
  1481  // operation by examine the Phi node at the merge block. So, we only interest
  1482  // in the slice operation if it is inside a for block or an if block.
  1483  // Otherwise it returns sliceInfo{0, sliceUnknown, 0}.
  1484  //
  1485  // For the following for block:
  1486  //
  1487  //	for len(a) > 4 {
  1488  //	    a = a[4:]
  1489  //	}
  1490  //
  1491  // vp = (Phi v3 v9)
  1492  // v5 = (SliceLen vp)
  1493  // v7 = (Add64 (Const64 [-4]) v5)
  1494  // v9 = (SliceMake _ v7 _)
  1495  //
  1496  // returns sliceInfo{-4, sliceInFor, 1}
  1497  //
  1498  // For a subsequent merge block after an if block:
  1499  //
  1500  //	if len(a) > 4 {
  1501  //	    a = a[4:]
  1502  //	}
  1503  //	a // here
  1504  //
  1505  // vp = (Phi v3 v9)
  1506  // v5 = (SliceLen v3)
  1507  // v7 = (Add64 (Const64 [-4]) v5)
  1508  // v9 = (SliceMake _ v7 _)
  1509  //
  1510  // returns sliceInfo{-4, sliceInIf, 1}
  1511  //
  1512  // Returns sliceInfo{0, sliceUnknown, 0} if it is not the slice
  1513  // operation we are interested in.
  1514  func getSliceInfo(vp *Value) (inf sliceInfo) {
  1515  	if vp.Op != OpPhi || len(vp.Args) != 2 {
  1516  		return
  1517  	}
  1518  	var i predIndex
  1519  	var l *Value // length for OpSliceMake
  1520  	if vp.Args[0].Op != OpSliceMake && vp.Args[1].Op == OpSliceMake {
  1521  		l = vp.Args[1].Args[1]
  1522  		i = 1
  1523  	} else if vp.Args[0].Op == OpSliceMake && vp.Args[1].Op != OpSliceMake {
  1524  		l = vp.Args[0].Args[1]
  1525  		i = 0
  1526  	} else {
  1527  		return
  1528  	}
  1529  	var op Op
  1530  	switch l.Op {
  1531  	case OpAdd64:
  1532  		op = OpConst64
  1533  	case OpAdd32:
  1534  		op = OpConst32
  1535  	default:
  1536  		return
  1537  	}
  1538  	if l.Args[0].Op == op && l.Args[1].Op == OpSliceLen && l.Args[1].Args[0] == vp {
  1539  		return sliceInfo{l.Args[0].AuxInt, sliceInFor, i}
  1540  	}
  1541  	if l.Args[1].Op == op && l.Args[0].Op == OpSliceLen && l.Args[0].Args[0] == vp {
  1542  		return sliceInfo{l.Args[1].AuxInt, sliceInFor, i}
  1543  	}
  1544  	if l.Args[0].Op == op && l.Args[1].Op == OpSliceLen && l.Args[1].Args[0] == vp.Args[1-i] {
  1545  		return sliceInfo{l.Args[0].AuxInt, sliceInIf, i}
  1546  	}
  1547  	if l.Args[1].Op == op && l.Args[0].Op == OpSliceLen && l.Args[0].Args[0] == vp.Args[1-i] {
  1548  		return sliceInfo{l.Args[1].AuxInt, sliceInIf, i}
  1549  	}
  1550  	return
  1551  }
  1552  
  1553  // prove removes redundant BlockIf branches that can be inferred
  1554  // from previous dominating comparisons.
  1555  //
  1556  // By far, the most common redundant pair are generated by bounds checking.
  1557  // For example for the code:
  1558  //
  1559  //	a[i] = 4
  1560  //	foo(a[i])
  1561  //
  1562  // The compiler will generate the following code:
  1563  //
  1564  //	if i >= len(a) {
  1565  //	    panic("not in bounds")
  1566  //	}
  1567  //	a[i] = 4
  1568  //	if i >= len(a) {
  1569  //	    panic("not in bounds")
  1570  //	}
  1571  //	foo(a[i])
  1572  //
  1573  // The second comparison i >= len(a) is clearly redundant because if the
  1574  // else branch of the first comparison is executed, we already know that i < len(a).
  1575  // The code for the second panic can be removed.
  1576  //
  1577  // prove works by finding contradictions and trimming branches whose
  1578  // conditions are unsatisfiable given the branches leading up to them.
  1579  // It tracks a "fact table" of branch conditions. For each branching
  1580  // block, it asserts the branch conditions that uniquely dominate that
  1581  // block, and then separately asserts the block's branch condition and
  1582  // its negation. If either leads to a contradiction, it can trim that
  1583  // successor.
  1584  func prove(f *Func) {
  1585  	// Find induction variables.
  1586  	var indVars map[*Block][]indVar
  1587  	for _, v := range findIndVar(f) {
  1588  		ind := v.ind
  1589  		if len(ind.Args) != 2 {
  1590  			// the rewrite code assumes there is only ever two parents to loops
  1591  			panic("unexpected induction with too many parents")
  1592  		}
  1593  
  1594  		nxt := v.nxt
  1595  		if !(ind.Uses == 2 && // 2 used by comparison and next
  1596  			nxt.Uses == 1) { // 1 used by induction
  1597  			// ind or nxt is used inside the loop, add it for the facts table
  1598  			if indVars == nil {
  1599  				indVars = make(map[*Block][]indVar)
  1600  			}
  1601  			indVars[v.entry] = append(indVars[v.entry], v)
  1602  			continue
  1603  		} else {
  1604  			// Since this induction variable is not used for anything but counting the iterations,
  1605  			// no point in putting it into the facts table.
  1606  		}
  1607  
  1608  		maybeRewriteLoopToDownwardCountingLoop(f, v)
  1609  	}
  1610  
  1611  	ft := newFactsTable(f)
  1612  	ft.checkpoint()
  1613  
  1614  	// Find length and capacity ops.
  1615  	for _, b := range f.Blocks {
  1616  		for _, v := range b.Values {
  1617  			if v.Uses == 0 {
  1618  				// We don't care about dead values.
  1619  				// (There can be some that are CSEd but not removed yet.)
  1620  				continue
  1621  			}
  1622  			switch v.Op {
  1623  			case OpSliceLen:
  1624  				if ft.lens == nil {
  1625  					ft.lens = map[ID]*Value{}
  1626  				}
  1627  				// Set all len Values for the same slice as equal in the poset.
  1628  				// The poset handles transitive relations, so Values related to
  1629  				// any OpSliceLen for this slice will be correctly related to others.
  1630  				if l, ok := ft.lens[v.Args[0].ID]; ok {
  1631  					ft.update(b, v, l, signed, eq)
  1632  				} else {
  1633  					ft.lens[v.Args[0].ID] = v
  1634  				}
  1635  			case OpSliceCap:
  1636  				if ft.caps == nil {
  1637  					ft.caps = map[ID]*Value{}
  1638  				}
  1639  				// Same as case OpSliceLen above, but for slice cap.
  1640  				if c, ok := ft.caps[v.Args[0].ID]; ok {
  1641  					ft.update(b, v, c, signed, eq)
  1642  				} else {
  1643  					ft.caps[v.Args[0].ID] = v
  1644  				}
  1645  			}
  1646  		}
  1647  	}
  1648  
  1649  	// current node state
  1650  	type walkState int
  1651  	const (
  1652  		descend walkState = iota
  1653  		restore
  1654  	)
  1655  	// work maintains the DFS stack.
  1656  	type bp struct {
  1657  		block *Block    // current handled block
  1658  		state walkState // what's to do
  1659  	}
  1660  	work := make([]bp, 0, 256)
  1661  	work = append(work, bp{
  1662  		block: f.Entry,
  1663  		state: descend,
  1664  	})
  1665  
  1666  	idom := f.Idom()
  1667  	sdom := f.Sdom()
  1668  
  1669  	// DFS on the dominator tree.
  1670  	//
  1671  	// For efficiency, we consider only the dominator tree rather
  1672  	// than the entire flow graph. On the way down, we consider
  1673  	// incoming branches and accumulate conditions that uniquely
  1674  	// dominate the current block. If we discover a contradiction,
  1675  	// we can eliminate the entire block and all of its children.
  1676  	// On the way back up, we consider outgoing branches that
  1677  	// haven't already been considered. This way we consider each
  1678  	// branch condition only once.
  1679  	for len(work) > 0 {
  1680  		node := work[len(work)-1]
  1681  		work = work[:len(work)-1]
  1682  		parent := idom[node.block.ID]
  1683  		branch := getBranch(sdom, parent, node.block)
  1684  
  1685  		switch node.state {
  1686  		case descend:
  1687  			ft.checkpoint()
  1688  
  1689  			// Entering the block, add facts about the induction variable
  1690  			// that is bound to this block.
  1691  			for _, iv := range indVars[node.block] {
  1692  				addIndVarRestrictions(ft, parent, iv)
  1693  			}
  1694  
  1695  			// Add results of reaching this block via a branch from
  1696  			// its immediate dominator (if any).
  1697  			if branch != unknown {
  1698  				addBranchRestrictions(ft, parent, branch)
  1699  			}
  1700  
  1701  			// Add slices of the same length start from current block.
  1702  			addSlicesOfSameLen(ft, node.block)
  1703  
  1704  			if ft.unsat {
  1705  				// node.block is unreachable.
  1706  				// Remove it and don't visit
  1707  				// its children.
  1708  				removeBranch(parent, branch)
  1709  				ft.restore()
  1710  				break
  1711  			}
  1712  			// Otherwise, we can now commit to
  1713  			// taking this branch. We'll restore
  1714  			// ft when we unwind.
  1715  
  1716  			ft.topoSortValuesInBlock(node.block)
  1717  
  1718  			for _, v := range node.block.Values {
  1719  				ft.flowLimit(v)
  1720  				// constant fold arguments before addValueFact to avoid v's v.Args learned facts time traveling into v's arguments.
  1721  				// in other words if v teaches us something about it's arguments,
  1722  				// we can't use that to optimize v's arguments since v hasn't ran yet.
  1723  				ft.constantFoldArguments(v)
  1724  				ft.addValueFact(node.block, v)
  1725  				ft.simplifyValue(node.block, v)
  1726  			}
  1727  
  1728  			ft.simplifyBlock(sdom, node.block)
  1729  
  1730  			work = append(work, bp{
  1731  				block: node.block,
  1732  				state: restore,
  1733  			})
  1734  			for s := sdom.Child(node.block); s != nil; s = sdom.Sibling(s) {
  1735  				work = append(work, bp{
  1736  					block: s,
  1737  					state: descend,
  1738  				})
  1739  			}
  1740  
  1741  		case restore:
  1742  			ft.restore()
  1743  		}
  1744  	}
  1745  
  1746  	ft.restore()
  1747  
  1748  	ft.cleanup(f)
  1749  }
  1750  
  1751  // initLimit sets initial constant limit for v.  This limit is based
  1752  // only on the operation itself, not any of its input arguments. This
  1753  // method is only used in two places, once when the prove pass startup
  1754  // and the other when a new ssa value is created, both for init. (unlike
  1755  // flowLimit, below, which computes additional constraints based on
  1756  // ranges of opcode arguments).
  1757  func initLimit(v *Value) limit {
  1758  	if v.Type.IsBoolean() {
  1759  		switch v.Op {
  1760  		case OpConstBool:
  1761  			b := v.AuxInt
  1762  			return limit{min: b, max: b, umin: uint64(b), umax: uint64(b)}
  1763  		default:
  1764  			return limit{min: 0, max: 1, umin: 0, umax: 1}
  1765  		}
  1766  	}
  1767  	if v.Type.IsPtrShaped() { // These are the types that EqPtr/NeqPtr operate on, except uintptr.
  1768  		switch v.Op {
  1769  		case OpConstNil:
  1770  			return limit{min: 0, max: 0, umin: 0, umax: 0}
  1771  		case OpAddr, OpLocalAddr: // TODO: others?
  1772  			l := noLimit()
  1773  			l.umin = 1
  1774  			return l
  1775  		default:
  1776  			return noLimit()
  1777  		}
  1778  	}
  1779  	if !v.Type.IsInteger() {
  1780  		return noLimit()
  1781  	}
  1782  
  1783  	// Default limits based on type.
  1784  	lim := noLimitForBitsize(uint(v.Type.Size()) * 8)
  1785  
  1786  	// Tighter limits on some opcodes.
  1787  	switch v.Op {
  1788  	// constants
  1789  	case OpConst64:
  1790  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(v.AuxInt), umax: uint64(v.AuxInt)}
  1791  	case OpConst32:
  1792  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint32(v.AuxInt)), umax: uint64(uint32(v.AuxInt))}
  1793  	case OpConst16:
  1794  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint16(v.AuxInt)), umax: uint64(uint16(v.AuxInt))}
  1795  	case OpConst8:
  1796  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint8(v.AuxInt)), umax: uint64(uint8(v.AuxInt))}
  1797  
  1798  	// extensions
  1799  	case OpZeroExt8to64, OpZeroExt8to32, OpZeroExt8to16:
  1800  		lim = lim.signedMinMax(0, 1<<8-1)
  1801  		lim = lim.unsignedMax(1<<8 - 1)
  1802  	case OpZeroExt16to64, OpZeroExt16to32:
  1803  		lim = lim.signedMinMax(0, 1<<16-1)
  1804  		lim = lim.unsignedMax(1<<16 - 1)
  1805  	case OpZeroExt32to64:
  1806  		lim = lim.signedMinMax(0, 1<<32-1)
  1807  		lim = lim.unsignedMax(1<<32 - 1)
  1808  	case OpSignExt8to64, OpSignExt8to32, OpSignExt8to16:
  1809  		lim = lim.signedMinMax(math.MinInt8, math.MaxInt8)
  1810  	case OpSignExt16to64, OpSignExt16to32:
  1811  		lim = lim.signedMinMax(math.MinInt16, math.MaxInt16)
  1812  	case OpSignExt32to64:
  1813  		lim = lim.signedMinMax(math.MinInt32, math.MaxInt32)
  1814  
  1815  	// math/bits intrinsics
  1816  	case OpCtz64, OpBitLen64, OpPopCount64,
  1817  		OpCtz32, OpBitLen32, OpPopCount32,
  1818  		OpCtz16, OpBitLen16, OpPopCount16,
  1819  		OpCtz8, OpBitLen8, OpPopCount8:
  1820  		lim = lim.unsignedMax(uint64(v.Args[0].Type.Size() * 8))
  1821  
  1822  	// bool to uint8 conversion
  1823  	case OpCvtBoolToUint8:
  1824  		lim = lim.unsignedMax(1)
  1825  
  1826  	// length operations
  1827  	case OpSliceLen, OpSliceCap:
  1828  		f := v.Block.Func
  1829  		elemSize := uint64(v.Args[0].Type.Elem().Size())
  1830  		if elemSize > 0 {
  1831  			heapSize := uint64(1)<<(uint64(f.Config.PtrSize)*8) - 1
  1832  			maximumElementsFittingInHeap := heapSize / elemSize
  1833  			lim = lim.unsignedMax(maximumElementsFittingInHeap)
  1834  		}
  1835  		fallthrough
  1836  	case OpStringLen:
  1837  		lim = lim.signedMin(0)
  1838  	}
  1839  
  1840  	// signed <-> unsigned propagation
  1841  	if lim.min >= 0 {
  1842  		lim = lim.unsignedMinMax(uint64(lim.min), uint64(lim.max))
  1843  	}
  1844  	if fitsInBitsU(lim.umax, uint(8*v.Type.Size()-1)) {
  1845  		lim = lim.signedMinMax(int64(lim.umin), int64(lim.umax))
  1846  	}
  1847  
  1848  	return lim
  1849  }
  1850  
  1851  // flowLimit updates the known limits of v in ft.
  1852  // flowLimit can use the ranges of input arguments.
  1853  //
  1854  // Note: this calculation only happens at the point the value is defined. We do not reevaluate
  1855  // it later. So for example:
  1856  //
  1857  //	v := x + y
  1858  //	if 0 <= x && x < 5 && 0 <= y && y < 5 { ... use v ... }
  1859  //
  1860  // we don't discover that the range of v is bounded in the conditioned
  1861  // block. We could recompute the range of v once we enter the block so
  1862  // we know that it is 0 <= v <= 8, but we don't have a mechanism to do
  1863  // that right now.
  1864  func (ft *factsTable) flowLimit(v *Value) {
  1865  	if !v.Type.IsInteger() {
  1866  		// TODO: boolean?
  1867  		return
  1868  	}
  1869  
  1870  	// Additional limits based on opcode and argument.
  1871  	// No need to repeat things here already done in initLimit.
  1872  	switch v.Op {
  1873  
  1874  	// extensions
  1875  	case OpZeroExt8to64, OpZeroExt8to32, OpZeroExt8to16, OpZeroExt16to64, OpZeroExt16to32, OpZeroExt32to64:
  1876  		a := ft.limits[v.Args[0].ID]
  1877  		ft.unsignedMinMax(v, a.umin, a.umax)
  1878  	case OpSignExt8to64, OpSignExt8to32, OpSignExt8to16, OpSignExt16to64, OpSignExt16to32, OpSignExt32to64:
  1879  		a := ft.limits[v.Args[0].ID]
  1880  		ft.signedMinMax(v, a.min, a.max)
  1881  	case OpTrunc64to8, OpTrunc64to16, OpTrunc64to32, OpTrunc32to8, OpTrunc32to16, OpTrunc16to8:
  1882  		a := ft.limits[v.Args[0].ID]
  1883  		if a.umax <= 1<<(uint64(v.Type.Size())*8)-1 {
  1884  			ft.unsignedMinMax(v, a.umin, a.umax)
  1885  		}
  1886  
  1887  	// math/bits
  1888  	case OpCtz64, OpCtz32, OpCtz16, OpCtz8:
  1889  		a := v.Args[0]
  1890  		al := ft.limits[a.ID]
  1891  		ft.newLimit(v, al.ctz(uint(a.Type.Size())*8))
  1892  
  1893  	case OpPopCount64, OpPopCount32, OpPopCount16, OpPopCount8:
  1894  		a := v.Args[0]
  1895  		al := ft.limits[a.ID]
  1896  		ft.newLimit(v, al.popcount(uint(a.Type.Size())*8))
  1897  
  1898  	case OpBitLen64, OpBitLen32, OpBitLen16, OpBitLen8:
  1899  		a := v.Args[0]
  1900  		al := ft.limits[a.ID]
  1901  		ft.newLimit(v, al.bitlen(uint(a.Type.Size())*8))
  1902  
  1903  	// Masks.
  1904  
  1905  	// TODO: if y.umax and y.umin share a leading bit pattern, y also has that leading bit pattern.
  1906  	// we could compare the patterns of always set bits in a and b and learn more about minimum and maximum.
  1907  	// But I doubt this help any real world code.
  1908  	case OpOr64, OpOr32, OpOr16, OpOr8:
  1909  		// OR can only make the value bigger and can't flip bits proved to be zero in both inputs.
  1910  		a := ft.limits[v.Args[0].ID]
  1911  		b := ft.limits[v.Args[1].ID]
  1912  		ft.unsignedMinMax(v,
  1913  			max(a.umin, b.umin),
  1914  			1<<bits.Len64(a.umax|b.umax)-1)
  1915  	case OpXor64, OpXor32, OpXor16, OpXor8:
  1916  		// XOR can't flip bits that are proved to be zero in both inputs.
  1917  		a := ft.limits[v.Args[0].ID]
  1918  		b := ft.limits[v.Args[1].ID]
  1919  		ft.unsignedMax(v, 1<<bits.Len64(a.umax|b.umax)-1)
  1920  	case OpCom64, OpCom32, OpCom16, OpCom8:
  1921  		a := ft.limits[v.Args[0].ID]
  1922  		ft.newLimit(v, a.com(uint(v.Type.Size())*8))
  1923  
  1924  	// Arithmetic.
  1925  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  1926  		a := ft.limits[v.Args[0].ID]
  1927  		b := ft.limits[v.Args[1].ID]
  1928  		ft.newLimit(v, a.add(b, uint(v.Type.Size())*8))
  1929  	case OpSub64, OpSub32, OpSub16, OpSub8:
  1930  		a := ft.limits[v.Args[0].ID]
  1931  		b := ft.limits[v.Args[1].ID]
  1932  		ft.newLimit(v, a.sub(b, uint(v.Type.Size())*8))
  1933  		ft.detectMod(v)
  1934  		ft.detectSliceLenRelation(v)
  1935  		ft.detectSubRelations(v)
  1936  	case OpNeg64, OpNeg32, OpNeg16, OpNeg8:
  1937  		a := ft.limits[v.Args[0].ID]
  1938  		bitsize := uint(v.Type.Size()) * 8
  1939  		ft.newLimit(v, a.neg(bitsize))
  1940  	case OpMul64, OpMul32, OpMul16, OpMul8:
  1941  		a := ft.limits[v.Args[0].ID]
  1942  		b := ft.limits[v.Args[1].ID]
  1943  		ft.newLimit(v, a.mul(b, uint(v.Type.Size())*8))
  1944  	case OpLsh64x64, OpLsh64x32, OpLsh64x16, OpLsh64x8,
  1945  		OpLsh32x64, OpLsh32x32, OpLsh32x16, OpLsh32x8,
  1946  		OpLsh16x64, OpLsh16x32, OpLsh16x16, OpLsh16x8,
  1947  		OpLsh8x64, OpLsh8x32, OpLsh8x16, OpLsh8x8:
  1948  		a := ft.limits[v.Args[0].ID]
  1949  		b := ft.limits[v.Args[1].ID]
  1950  		bitsize := uint(v.Type.Size()) * 8
  1951  		ft.newLimit(v, a.mul(b.exp2(bitsize), bitsize))
  1952  	case OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8,
  1953  		OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  1954  		OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  1955  		OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8:
  1956  		a := ft.limits[v.Args[0].ID]
  1957  		b := ft.limits[v.Args[1].ID]
  1958  		if b.min >= 0 {
  1959  			// Shift of negative makes a value closer to 0 (greater),
  1960  			// so if a.min is negative, v.min is a.min>>b.min instead of a.min>>b.max,
  1961  			// and similarly if a.max is negative, v.max is a.max>>b.max.
  1962  			// Easier to compute min and max of both than to write sign logic.
  1963  			vmin := min(a.min>>b.min, a.min>>b.max)
  1964  			vmax := max(a.max>>b.min, a.max>>b.max)
  1965  			ft.signedMinMax(v, vmin, vmax)
  1966  		}
  1967  	case OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8,
  1968  		OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  1969  		OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  1970  		OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8:
  1971  		a := ft.limits[v.Args[0].ID]
  1972  		b := ft.limits[v.Args[1].ID]
  1973  		if b.min >= 0 {
  1974  			ft.unsignedMinMax(v, a.umin>>b.max, a.umax>>b.min)
  1975  		}
  1976  	case OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  1977  		a := ft.limits[v.Args[0].ID]
  1978  		b := ft.limits[v.Args[1].ID]
  1979  		if !(a.nonnegative() && b.nonnegative()) {
  1980  			// TODO: we could handle signed limits but I didn't bother.
  1981  			break
  1982  		}
  1983  		fallthrough
  1984  	case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u:
  1985  		a := ft.limits[v.Args[0].ID]
  1986  		b := ft.limits[v.Args[1].ID]
  1987  		lim := noLimit()
  1988  		if b.umax > 0 {
  1989  			lim = lim.unsignedMin(a.umin / b.umax)
  1990  		}
  1991  		if b.umin > 0 {
  1992  			lim = lim.unsignedMax(a.umax / b.umin)
  1993  		}
  1994  		ft.newLimit(v, lim)
  1995  	case OpMod64, OpMod32, OpMod16, OpMod8:
  1996  		ft.modLimit(true, v, v.Args[0], v.Args[1])
  1997  	case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
  1998  		ft.modLimit(false, v, v.Args[0], v.Args[1])
  1999  
  2000  	case OpPhi:
  2001  		// Compute the union of all the input phis.
  2002  		// Often this will convey no information, because the block
  2003  		// is not dominated by its predecessors and hence the
  2004  		// phi arguments might not have been processed yet. But if
  2005  		// the values are declared earlier, it may help. e.g., for
  2006  		//    v = phi(c3, c5)
  2007  		// where c3 = OpConst [3] and c5 = OpConst [5] are
  2008  		// defined in the entry block, we can derive [3,5]
  2009  		// as the limit for v.
  2010  		l := ft.limits[v.Args[0].ID]
  2011  		for _, a := range v.Args[1:] {
  2012  			l2 := ft.limits[a.ID]
  2013  			l.min = min(l.min, l2.min)
  2014  			l.max = max(l.max, l2.max)
  2015  			l.umin = min(l.umin, l2.umin)
  2016  			l.umax = max(l.umax, l2.umax)
  2017  		}
  2018  		ft.newLimit(v, l)
  2019  	}
  2020  }
  2021  
  2022  // detectSliceLenRelation matches the pattern where
  2023  //  1. v := slicelen - index, OR v := slicecap - index
  2024  //     AND
  2025  //  2. index <= slicelen - K
  2026  //     THEN
  2027  //
  2028  // slicecap - index >= slicelen - index >= K
  2029  //
  2030  // Note that "index" is not used for indexing in this pattern, but
  2031  // in the motivating example (chunked slice iteration) it is.
  2032  func (ft *factsTable) detectSliceLenRelation(v *Value) {
  2033  	if v.Op != OpSub64 {
  2034  		return
  2035  	}
  2036  
  2037  	if !(v.Args[0].Op == OpSliceLen || v.Args[0].Op == OpStringLen || v.Args[0].Op == OpSliceCap) {
  2038  		return
  2039  	}
  2040  
  2041  	index := v.Args[1]
  2042  	if !ft.isNonNegative(index) {
  2043  		return
  2044  	}
  2045  	slice := v.Args[0].Args[0]
  2046  
  2047  	for o := ft.orderings[index.ID]; o != nil; o = o.next {
  2048  		if o.d != signed {
  2049  			continue
  2050  		}
  2051  		or := o.r
  2052  		if or != lt && or != lt|eq {
  2053  			continue
  2054  		}
  2055  		ow := o.w
  2056  		if ow.Op != OpAdd64 && ow.Op != OpSub64 {
  2057  			continue
  2058  		}
  2059  		var lenOffset *Value
  2060  		if bound := ow.Args[0]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2061  			lenOffset = ow.Args[1]
  2062  		} else if bound := ow.Args[1]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2063  			// Do not infer K - slicelen, see issue #76709.
  2064  			if ow.Op == OpAdd64 {
  2065  				lenOffset = ow.Args[0]
  2066  			}
  2067  		}
  2068  		if lenOffset == nil || lenOffset.Op != OpConst64 {
  2069  			continue
  2070  		}
  2071  		K := lenOffset.AuxInt
  2072  		if ow.Op == OpAdd64 {
  2073  			K = -K
  2074  		}
  2075  		if K < 0 {
  2076  			continue
  2077  		}
  2078  		if or == lt {
  2079  			K++
  2080  		}
  2081  		if K < 0 { // We hate thinking about overflow
  2082  			continue
  2083  		}
  2084  		ft.signedMin(v, K)
  2085  	}
  2086  }
  2087  
  2088  // v must be Sub{64,32,16,8}.
  2089  func (ft *factsTable) detectSubRelations(v *Value) {
  2090  	// v = x-y
  2091  	x := v.Args[0]
  2092  	y := v.Args[1]
  2093  	if x == y {
  2094  		ft.signedMinMax(v, 0, 0)
  2095  		return
  2096  	}
  2097  	xLim := ft.limits[x.ID]
  2098  	yLim := ft.limits[y.ID]
  2099  
  2100  	// Check if we might wrap around. If so, give up.
  2101  	width := uint(v.Type.Size()) * 8
  2102  
  2103  	// v >= 1 in the signed domain?
  2104  	var vSignedMinOne bool
  2105  
  2106  	// Signed optimizations
  2107  	if _, ok := safeSub(xLim.min, yLim.max, width); ok {
  2108  		// Large abs negative y can also overflow
  2109  		if _, ok := safeSub(xLim.max, yLim.min, width); ok {
  2110  			// x-y won't overflow
  2111  
  2112  			// Subtracting a positive non-zero number only makes
  2113  			// things smaller. If it's positive or zero, it might
  2114  			// also do nothing (x-0 == v).
  2115  			if yLim.min > 0 {
  2116  				ft.update(v.Block, v, x, signed, lt)
  2117  			} else if yLim.min == 0 {
  2118  				ft.update(v.Block, v, x, signed, lt|eq)
  2119  			}
  2120  
  2121  			// Subtracting a number from a bigger one
  2122  			// can't go below 1. If the numbers might be
  2123  			// equal, then it can't go below 0.
  2124  			//
  2125  			// This requires the overflow checks because
  2126  			// large negative y can cause an overflow.
  2127  			if ft.orderS.Ordered(y, x) {
  2128  				ft.signedMin(v, 1)
  2129  				vSignedMinOne = true
  2130  			} else if ft.orderS.OrderedOrEqual(y, x) {
  2131  				ft.setNonNegative(v)
  2132  			}
  2133  		}
  2134  	}
  2135  
  2136  	// Unsigned optimizations
  2137  	if _, ok := safeSubU(xLim.umin, yLim.umax, width); ok {
  2138  		if yLim.umin > 0 {
  2139  			ft.update(v.Block, v, x, unsigned, lt)
  2140  		} else {
  2141  			ft.update(v.Block, v, x, unsigned, lt|eq)
  2142  		}
  2143  	}
  2144  
  2145  	// Proving v >= 1 in the signed domain automatically
  2146  	// proves it in the unsigned domain, so we can skip it.
  2147  	//
  2148  	// We don't need overflow checks here, since if y < x,
  2149  	// then x-y can never overflow for uint.
  2150  	if !vSignedMinOne && ft.orderU.Ordered(y, x) {
  2151  		ft.unsignedMin(v, 1)
  2152  	}
  2153  }
  2154  
  2155  // x%d has been rewritten to x - (x/d)*d.
  2156  func (ft *factsTable) detectMod(v *Value) {
  2157  	var opDiv, opDivU, opMul, opConst Op
  2158  	switch v.Op {
  2159  	case OpSub64:
  2160  		opDiv = OpDiv64
  2161  		opDivU = OpDiv64u
  2162  		opMul = OpMul64
  2163  		opConst = OpConst64
  2164  	case OpSub32:
  2165  		opDiv = OpDiv32
  2166  		opDivU = OpDiv32u
  2167  		opMul = OpMul32
  2168  		opConst = OpConst32
  2169  	case OpSub16:
  2170  		opDiv = OpDiv16
  2171  		opDivU = OpDiv16u
  2172  		opMul = OpMul16
  2173  		opConst = OpConst16
  2174  	case OpSub8:
  2175  		opDiv = OpDiv8
  2176  		opDivU = OpDiv8u
  2177  		opMul = OpMul8
  2178  		opConst = OpConst8
  2179  	}
  2180  
  2181  	mul := v.Args[1]
  2182  	if mul.Op != opMul {
  2183  		return
  2184  	}
  2185  	div, con := mul.Args[0], mul.Args[1]
  2186  	if div.Op == opConst {
  2187  		div, con = con, div
  2188  	}
  2189  	if con.Op != opConst || (div.Op != opDiv && div.Op != opDivU) || div.Args[0] != v.Args[0] || div.Args[1].Op != opConst || div.Args[1].AuxInt != con.AuxInt {
  2190  		return
  2191  	}
  2192  	ft.modLimit(div.Op == opDiv, v, v.Args[0], con)
  2193  }
  2194  
  2195  // modLimit sets v with facts derived from v = p % q.
  2196  func (ft *factsTable) modLimit(signed bool, v, p, q *Value) {
  2197  	a := ft.limits[p.ID]
  2198  	b := ft.limits[q.ID]
  2199  	if signed {
  2200  		if a.min < 0 && b.min > 0 {
  2201  			ft.signedMinMax(v, -(b.max - 1), b.max-1)
  2202  			return
  2203  		}
  2204  		if !(a.nonnegative() && b.nonnegative()) {
  2205  			// TODO: we could handle signed limits but I didn't bother.
  2206  			return
  2207  		}
  2208  		if a.min >= 0 && b.min > 0 {
  2209  			ft.setNonNegative(v)
  2210  		}
  2211  	}
  2212  	// Underflow in the arithmetic below is ok, it gives to MaxUint64 which does nothing to the limit.
  2213  	ft.unsignedMax(v, min(a.umax, b.umax-1))
  2214  }
  2215  
  2216  // getBranch returns the range restrictions added by p
  2217  // when reaching b. p is the immediate dominator of b.
  2218  func getBranch(sdom SparseTree, p *Block, b *Block) branch {
  2219  	if p == nil {
  2220  		return unknown
  2221  	}
  2222  	switch p.Kind {
  2223  	case block.BlockIf:
  2224  		// If p and p.Succs[0] are dominators it means that every path
  2225  		// from entry to b passes through p and p.Succs[0]. We care that
  2226  		// no path from entry to b passes through p.Succs[1]. If p.Succs[0]
  2227  		// has one predecessor then (apart from the degenerate case),
  2228  		// there is no path from entry that can reach b through p.Succs[1].
  2229  		// TODO: how about p->yes->b->yes, i.e. a loop in yes.
  2230  		if sdom.IsAncestorEq(p.Succs[0].b, b) && len(p.Succs[0].b.Preds) == 1 {
  2231  			return positive
  2232  		}
  2233  		if sdom.IsAncestorEq(p.Succs[1].b, b) && len(p.Succs[1].b.Preds) == 1 {
  2234  			return negative
  2235  		}
  2236  	case block.BlockJumpTable:
  2237  		// TODO: this loop can lead to quadratic behavior, as
  2238  		// getBranch can be called len(p.Succs) times.
  2239  		for i, e := range p.Succs {
  2240  			if sdom.IsAncestorEq(e.b, b) && len(e.b.Preds) == 1 {
  2241  				return jumpTable0 + branch(i)
  2242  			}
  2243  		}
  2244  	}
  2245  	return unknown
  2246  }
  2247  
  2248  // addIndVarRestrictions updates the factsTables ft with the facts
  2249  // learned from the induction variable indVar which drives the loop
  2250  // starting in Block b.
  2251  func addIndVarRestrictions(ft *factsTable, b *Block, iv indVar) {
  2252  	d := signed
  2253  	if ft.isNonNegative(iv.min) && ft.isNonNegative(iv.max) {
  2254  		d |= unsigned
  2255  	}
  2256  
  2257  	if iv.flags&indVarMinExc == 0 {
  2258  		addRestrictions(b, ft, d, iv.min, iv.ind, lt|eq)
  2259  	} else {
  2260  		addRestrictions(b, ft, d, iv.min, iv.ind, lt)
  2261  	}
  2262  
  2263  	if iv.flags&indVarMaxInc == 0 {
  2264  		addRestrictions(b, ft, d, iv.ind, iv.max, lt)
  2265  	} else {
  2266  		addRestrictions(b, ft, d, iv.ind, iv.max, lt|eq)
  2267  	}
  2268  }
  2269  
  2270  // addBranchRestrictions updates the factsTables ft with the facts learned when
  2271  // branching from Block b in direction br.
  2272  func addBranchRestrictions(ft *factsTable, b *Block, br branch) {
  2273  	c := b.Controls[0]
  2274  	switch {
  2275  	case br == negative:
  2276  		ft.booleanFalse(c)
  2277  	case br == positive:
  2278  		ft.booleanTrue(c)
  2279  	case br >= jumpTable0:
  2280  		idx := br - jumpTable0
  2281  		val := int64(idx)
  2282  		if v, off := isConstDelta(c); v != nil {
  2283  			// Establish the bound on the underlying value we're switching on,
  2284  			// not on the offset-ed value used as the jump table index.
  2285  			c = v
  2286  			val -= off
  2287  		}
  2288  		ft.newLimit(c, limit{min: val, max: val, umin: uint64(val), umax: uint64(val)})
  2289  	default:
  2290  		panic("unknown branch")
  2291  	}
  2292  }
  2293  
  2294  // addRestrictions updates restrictions from the immediate
  2295  // dominating block (p) using r.
  2296  func addRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r relation) {
  2297  	if t == 0 {
  2298  		// Trivial case: nothing to do.
  2299  		// Should not happen, but just in case.
  2300  		return
  2301  	}
  2302  	for i := domain(1); i <= t; i <<= 1 {
  2303  		if t&i == 0 {
  2304  			continue
  2305  		}
  2306  		ft.update(parent, v, w, i, r)
  2307  	}
  2308  }
  2309  
  2310  func unsignedAddOverflows(a, b uint64, t *types.Type) bool {
  2311  	switch t.Size() {
  2312  	case 8:
  2313  		return a+b < a
  2314  	case 4:
  2315  		return a+b > math.MaxUint32
  2316  	case 2:
  2317  		return a+b > math.MaxUint16
  2318  	case 1:
  2319  		return a+b > math.MaxUint8
  2320  	default:
  2321  		panic("unreachable")
  2322  	}
  2323  }
  2324  
  2325  func signedAddOverflowsOrUnderflows(a, b int64, t *types.Type) bool {
  2326  	r := a + b
  2327  	switch t.Size() {
  2328  	case 8:
  2329  		return (a >= 0 && b >= 0 && r < 0) || (a < 0 && b < 0 && r >= 0)
  2330  	case 4:
  2331  		return r < math.MinInt32 || math.MaxInt32 < r
  2332  	case 2:
  2333  		return r < math.MinInt16 || math.MaxInt16 < r
  2334  	case 1:
  2335  		return r < math.MinInt8 || math.MaxInt8 < r
  2336  	default:
  2337  		panic("unreachable")
  2338  	}
  2339  }
  2340  
  2341  func unsignedSubUnderflows(a, b uint64) bool {
  2342  	return a < b
  2343  }
  2344  
  2345  // checkForChunkedIndexBounds looks for index expressions of the form
  2346  // A[i+delta] where delta < K and i <= len(A)-K.  That is, this is a chunked
  2347  // iteration where the index is not directly compared to the length.
  2348  // if isReslice, then delta can be equal to K.
  2349  func checkForChunkedIndexBounds(ft *factsTable, b *Block, index, bound *Value, isReslice bool) bool {
  2350  	if bound.Op != OpSliceLen && bound.Op != OpStringLen && bound.Op != OpSliceCap {
  2351  		return false
  2352  	}
  2353  
  2354  	// this is a slice bounds check against len or capacity,
  2355  	// and refers back to a prior check against length, which
  2356  	// will also work for the cap since that is not smaller
  2357  	// than the length.
  2358  
  2359  	slice := bound.Args[0]
  2360  	lim := ft.limits[index.ID]
  2361  	if lim.min < 0 {
  2362  		return false
  2363  	}
  2364  	i, delta := isConstDelta(index)
  2365  	if i == nil {
  2366  		return false
  2367  	}
  2368  	if delta < 0 {
  2369  		return false
  2370  	}
  2371  	// special case for blocked iteration over a slice.
  2372  	// slicelen > i + delta && <==== if clauses above
  2373  	// && index >= 0           <==== if clause above
  2374  	// delta >= 0 &&           <==== if clause above
  2375  	// slicelen-K >/>= x       <==== checked below
  2376  	// && K >=/> delta         <==== checked below
  2377  	// then v > w
  2378  	// example: i <=/< len - 4/3 means i+{0,1,2,3} are legal indices
  2379  	for o := ft.orderings[i.ID]; o != nil; o = o.next {
  2380  		if o.d != signed {
  2381  			continue
  2382  		}
  2383  		if ow := o.w; ow.Op == OpAdd64 {
  2384  			var lenOffset *Value
  2385  			if bound := ow.Args[0]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2386  				lenOffset = ow.Args[1]
  2387  			} else if bound := ow.Args[1]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2388  				lenOffset = ow.Args[0]
  2389  			}
  2390  			if lenOffset == nil || lenOffset.Op != OpConst64 {
  2391  				continue
  2392  			}
  2393  			if K := -lenOffset.AuxInt; K >= 0 {
  2394  				or := o.r
  2395  				if isReslice {
  2396  					K++
  2397  				}
  2398  				if or == lt {
  2399  					or = lt | eq
  2400  					K++
  2401  				}
  2402  				if K < 0 { // We hate thinking about overflow
  2403  					continue
  2404  				}
  2405  
  2406  				if delta < K && or == lt|eq {
  2407  					return true
  2408  				}
  2409  			}
  2410  		}
  2411  	}
  2412  	return false
  2413  }
  2414  
  2415  func (ft *factsTable) addValueFact(b *Block, v *Value) {
  2416  	switch v.Op {
  2417  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2418  		x := ft.limits[v.Args[0].ID]
  2419  		y := ft.limits[v.Args[1].ID]
  2420  		if !unsignedAddOverflows(x.umax, y.umax, v.Type) {
  2421  			r := gt
  2422  			if x.maybeZero() {
  2423  				r |= eq
  2424  			}
  2425  			ft.update(b, v, v.Args[1], unsigned, r)
  2426  			r = gt
  2427  			if y.maybeZero() {
  2428  				r |= eq
  2429  			}
  2430  			ft.update(b, v, v.Args[0], unsigned, r)
  2431  		}
  2432  		if x.min >= 0 && !signedAddOverflowsOrUnderflows(x.max, y.max, v.Type) {
  2433  			r := gt
  2434  			if x.maybeZero() {
  2435  				r |= eq
  2436  			}
  2437  			ft.update(b, v, v.Args[1], signed, r)
  2438  		}
  2439  		if y.min >= 0 && !signedAddOverflowsOrUnderflows(x.max, y.max, v.Type) {
  2440  			r := gt
  2441  			if y.maybeZero() {
  2442  				r |= eq
  2443  			}
  2444  			ft.update(b, v, v.Args[0], signed, r)
  2445  		}
  2446  		if x.max <= 0 && !signedAddOverflowsOrUnderflows(x.min, y.min, v.Type) {
  2447  			r := lt
  2448  			if x.maybeZero() {
  2449  				r |= eq
  2450  			}
  2451  			ft.update(b, v, v.Args[1], signed, r)
  2452  		}
  2453  		if y.max <= 0 && !signedAddOverflowsOrUnderflows(x.min, y.min, v.Type) {
  2454  			r := lt
  2455  			if y.maybeZero() {
  2456  				r |= eq
  2457  			}
  2458  			ft.update(b, v, v.Args[0], signed, r)
  2459  		}
  2460  	case OpSub64, OpSub32, OpSub16, OpSub8:
  2461  		x := ft.limits[v.Args[0].ID]
  2462  		y := ft.limits[v.Args[1].ID]
  2463  		if !unsignedSubUnderflows(x.umin, y.umax) {
  2464  			r := lt
  2465  			if y.maybeZero() {
  2466  				r |= eq
  2467  			}
  2468  			ft.update(b, v, v.Args[0], unsigned, r)
  2469  		}
  2470  		// FIXME: we could also do signed facts but the overflow checks are much trickier and I don't need it yet.
  2471  	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
  2472  		ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2473  		ft.update(b, v, v.Args[1], unsigned, lt|eq)
  2474  		if ft.isNonNegative(v.Args[0]) {
  2475  			ft.update(b, v, v.Args[0], signed, lt|eq)
  2476  		}
  2477  		if ft.isNonNegative(v.Args[1]) {
  2478  			ft.update(b, v, v.Args[1], signed, lt|eq)
  2479  		}
  2480  	case OpOr64, OpOr32, OpOr16, OpOr8:
  2481  		// TODO: investigate how to always add facts without much slowdown, see issue #57959
  2482  		//ft.update(b, v, v.Args[0], unsigned, gt|eq)
  2483  		//ft.update(b, v, v.Args[1], unsigned, gt|eq)
  2484  	case OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  2485  		if !ft.isNonNegative(v.Args[1]) {
  2486  			break
  2487  		}
  2488  		fallthrough
  2489  	case OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8,
  2490  		OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  2491  		OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  2492  		OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8:
  2493  		if !ft.isNonNegative(v.Args[0]) {
  2494  			break
  2495  		}
  2496  		fallthrough
  2497  	case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
  2498  		OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
  2499  		OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  2500  		OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  2501  		OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8:
  2502  		switch add := v.Args[0]; add.Op {
  2503  		// round-up division pattern; given:
  2504  		// v = (x + y) / z
  2505  		// if y < z then v <= x
  2506  		case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2507  			z := v.Args[1]
  2508  			zl := ft.limits[z.ID]
  2509  			var uminDivisor uint64
  2510  			switch v.Op {
  2511  			case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
  2512  				OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  2513  				uminDivisor = zl.umin
  2514  			case OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
  2515  				OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  2516  				OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  2517  				OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8,
  2518  				OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8,
  2519  				OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  2520  				OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  2521  				OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8:
  2522  				uminDivisor = 1 << zl.umin
  2523  			default:
  2524  				panic("unreachable")
  2525  			}
  2526  
  2527  			x := add.Args[0]
  2528  			xl := ft.limits[x.ID]
  2529  			y := add.Args[1]
  2530  			yl := ft.limits[y.ID]
  2531  			if !unsignedAddOverflows(xl.umax, yl.umax, add.Type) {
  2532  				if xl.umax < uminDivisor {
  2533  					ft.update(b, v, y, unsigned, lt|eq)
  2534  				}
  2535  				if yl.umax < uminDivisor {
  2536  					ft.update(b, v, x, unsigned, lt|eq)
  2537  				}
  2538  			}
  2539  		}
  2540  		ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2541  	case OpMod64, OpMod32, OpMod16, OpMod8:
  2542  		if !ft.isNonNegative(v.Args[0]) || !ft.isNonNegative(v.Args[1]) {
  2543  			break
  2544  		}
  2545  		fallthrough
  2546  	case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
  2547  		ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2548  		// Note: we have to be careful that this doesn't imply
  2549  		// that the modulus is >0, which isn't true until *after*
  2550  		// the mod instruction executes (and thus panics if the
  2551  		// modulus is 0). See issue 67625.
  2552  		ft.update(b, v, v.Args[1], unsigned, lt)
  2553  	case OpStringLen:
  2554  		if v.Args[0].Op == OpStringMake {
  2555  			ft.update(b, v, v.Args[0].Args[1], signed, eq)
  2556  		}
  2557  	case OpSliceLen:
  2558  		if v.Args[0].Op == OpSliceMake {
  2559  			ft.update(b, v, v.Args[0].Args[1], signed, eq)
  2560  		}
  2561  	case OpSliceCap:
  2562  		if v.Args[0].Op == OpSliceMake {
  2563  			ft.update(b, v, v.Args[0].Args[2], signed, eq)
  2564  		}
  2565  	case OpIsInBounds:
  2566  		if checkForChunkedIndexBounds(ft, b, v.Args[0], v.Args[1], false) {
  2567  			if b.Func.pass.debug > 0 {
  2568  				b.Func.Warnl(v.Pos, "Proved %s for blocked indexing", v.Op)
  2569  			}
  2570  			ft.booleanTrue(v)
  2571  		}
  2572  	case OpIsSliceInBounds:
  2573  		if checkForChunkedIndexBounds(ft, b, v.Args[0], v.Args[1], true) {
  2574  			if b.Func.pass.debug > 0 {
  2575  				b.Func.Warnl(v.Pos, "Proved %s for blocked reslicing", v.Op)
  2576  			}
  2577  			ft.booleanTrue(v)
  2578  		}
  2579  	case OpPhi:
  2580  		addLocalFactsPhi(ft, v)
  2581  	}
  2582  }
  2583  
  2584  func addLocalFactsPhi(ft *factsTable, v *Value) {
  2585  	// Look for phis that implement min/max.
  2586  	//   z:
  2587  	//      c = Less64 x y (or other Less/Leq operation)
  2588  	//      If c -> bx by
  2589  	//   bx: <- z
  2590  	//       -> b ...
  2591  	//   by: <- z
  2592  	//      -> b ...
  2593  	//   b: <- bx by
  2594  	//      v = Phi x y
  2595  	// Then v is either min or max of x,y.
  2596  	// If it is the min, then we deduce v <= x && v <= y.
  2597  	// If it is the max, then we deduce v >= x && v >= y.
  2598  	// The min case is useful for the copy builtin, see issue 16833.
  2599  	if len(v.Args) != 2 {
  2600  		return
  2601  	}
  2602  	b := v.Block
  2603  	x := v.Args[0]
  2604  	y := v.Args[1]
  2605  	bx := b.Preds[0].b
  2606  	by := b.Preds[1].b
  2607  	var z *Block // branch point
  2608  	switch {
  2609  	case bx == by: // bx == by == z case
  2610  		z = bx
  2611  	case by.uniquePred() == bx: // bx == z case
  2612  		z = bx
  2613  	case bx.uniquePred() == by: // by == z case
  2614  		z = by
  2615  	case bx.uniquePred() == by.uniquePred():
  2616  		z = bx.uniquePred()
  2617  	}
  2618  	if z == nil || z.Kind != block.BlockIf {
  2619  		return
  2620  	}
  2621  	c := z.Controls[0]
  2622  	if len(c.Args) != 2 {
  2623  		return
  2624  	}
  2625  	var isMin bool // if c, a less-than comparison, is true, phi chooses x.
  2626  	if bx == z {
  2627  		isMin = b.Preds[0].i == 0
  2628  	} else {
  2629  		isMin = bx.Preds[0].i == 0
  2630  	}
  2631  	if c.Args[0] == x && c.Args[1] == y {
  2632  		// ok
  2633  	} else if c.Args[0] == y && c.Args[1] == x {
  2634  		// Comparison is reversed from how the values are listed in the Phi.
  2635  		isMin = !isMin
  2636  	} else {
  2637  		// Not comparing x and y.
  2638  		return
  2639  	}
  2640  	var dom domain
  2641  	switch c.Op {
  2642  	case OpLess64, OpLess32, OpLess16, OpLess8, OpLeq64, OpLeq32, OpLeq16, OpLeq8:
  2643  		dom = signed
  2644  	case OpLess64U, OpLess32U, OpLess16U, OpLess8U, OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U:
  2645  		dom = unsigned
  2646  	default:
  2647  		return
  2648  	}
  2649  	var rel relation
  2650  	if isMin {
  2651  		rel = lt | eq
  2652  	} else {
  2653  		rel = gt | eq
  2654  	}
  2655  	ft.update(b, v, x, dom, rel)
  2656  	ft.update(b, v, y, dom, rel)
  2657  }
  2658  
  2659  var ctzNonZeroOp = map[Op]Op{
  2660  	OpCtz8:  OpCtz8NonZero,
  2661  	OpCtz16: OpCtz16NonZero,
  2662  	OpCtz32: OpCtz32NonZero,
  2663  	OpCtz64: OpCtz64NonZero,
  2664  }
  2665  var mostNegativeDividend = map[Op]int64{
  2666  	OpDiv16: -1 << 15,
  2667  	OpMod16: -1 << 15,
  2668  	OpDiv32: -1 << 31,
  2669  	OpMod32: -1 << 31,
  2670  	OpDiv64: -1 << 63,
  2671  	OpMod64: -1 << 63,
  2672  }
  2673  var unsignedOp = map[Op]Op{
  2674  	OpDiv8:     OpDiv8u,
  2675  	OpDiv16:    OpDiv16u,
  2676  	OpDiv32:    OpDiv32u,
  2677  	OpDiv64:    OpDiv64u,
  2678  	OpMod8:     OpMod8u,
  2679  	OpMod16:    OpMod16u,
  2680  	OpMod32:    OpMod32u,
  2681  	OpMod64:    OpMod64u,
  2682  	OpRsh8x8:   OpRsh8Ux8,
  2683  	OpRsh8x16:  OpRsh8Ux16,
  2684  	OpRsh8x32:  OpRsh8Ux32,
  2685  	OpRsh8x64:  OpRsh8Ux64,
  2686  	OpRsh16x8:  OpRsh16Ux8,
  2687  	OpRsh16x16: OpRsh16Ux16,
  2688  	OpRsh16x32: OpRsh16Ux32,
  2689  	OpRsh16x64: OpRsh16Ux64,
  2690  	OpRsh32x8:  OpRsh32Ux8,
  2691  	OpRsh32x16: OpRsh32Ux16,
  2692  	OpRsh32x32: OpRsh32Ux32,
  2693  	OpRsh32x64: OpRsh32Ux64,
  2694  	OpRsh64x8:  OpRsh64Ux8,
  2695  	OpRsh64x16: OpRsh64Ux16,
  2696  	OpRsh64x32: OpRsh64Ux32,
  2697  	OpRsh64x64: OpRsh64Ux64,
  2698  }
  2699  
  2700  var bytesizeToConst = [...]Op{
  2701  	8 / 8:  OpConst8,
  2702  	16 / 8: OpConst16,
  2703  	32 / 8: OpConst32,
  2704  	64 / 8: OpConst64,
  2705  }
  2706  var bytesizeToNeq = [...]Op{
  2707  	8 / 8:  OpNeq8,
  2708  	16 / 8: OpNeq16,
  2709  	32 / 8: OpNeq32,
  2710  	64 / 8: OpNeq64,
  2711  }
  2712  var bytesizeToAnd = [...]Op{
  2713  	8 / 8:  OpAnd8,
  2714  	16 / 8: OpAnd16,
  2715  	32 / 8: OpAnd32,
  2716  	64 / 8: OpAnd64,
  2717  }
  2718  
  2719  var invertEqNeqOp = map[Op]Op{
  2720  	OpEq8:  OpNeq8,
  2721  	OpNeq8: OpEq8,
  2722  
  2723  	OpEq16:  OpNeq16,
  2724  	OpNeq16: OpEq16,
  2725  
  2726  	OpEq32:  OpNeq32,
  2727  	OpNeq32: OpEq32,
  2728  
  2729  	OpEq64:  OpNeq64,
  2730  	OpNeq64: OpEq64,
  2731  }
  2732  
  2733  func (ft *factsTable) simplifyValue(b *Block, v *Value) {
  2734  	switch v.Op {
  2735  	case OpStaticLECall:
  2736  		if b.Func.pass.debug > 0 && len(v.Args) == 2 {
  2737  			fn := auxToCall(v.Aux).Fn
  2738  			if fn != nil && strings.Contains(fn.String(), "prove") {
  2739  				// Print bounds of any argument to single-arg function with "prove" in name,
  2740  				// for debugging and especially for test/prove.go.
  2741  				// (v.Args[1] is mem).
  2742  				x := v.Args[0]
  2743  				b.Func.Warnl(v.Pos, "Proved %v (%v)", ft.limits[x.ID], x)
  2744  			}
  2745  		}
  2746  	case OpSlicemask:
  2747  		// Replace OpSlicemask operations in b with constants where possible.
  2748  		cap := v.Args[0]
  2749  		x, delta := isConstDelta(cap)
  2750  		if x != nil {
  2751  			// slicemask(x + y)
  2752  			// if x is larger than -y (y is negative), then slicemask is -1.
  2753  			lim := ft.limits[x.ID]
  2754  			if lim.umin > uint64(-delta) {
  2755  				if v.Type.Size() == 8 {
  2756  					v.reset(OpConst64)
  2757  				} else {
  2758  					v.reset(OpConst32)
  2759  				}
  2760  				if b.Func.pass.debug > 0 {
  2761  					b.Func.Warnl(v.Pos, "Proved slicemask not needed")
  2762  				}
  2763  				v.AuxInt = -1
  2764  			}
  2765  			break
  2766  		}
  2767  		lim := ft.limits[cap.ID]
  2768  		if lim.umin > 0 {
  2769  			if v.Type.Size() == 8 {
  2770  				v.reset(OpConst64)
  2771  			} else {
  2772  				v.reset(OpConst32)
  2773  			}
  2774  			if b.Func.pass.debug > 0 {
  2775  				b.Func.Warnl(v.Pos, "Proved slicemask not needed (by limit)")
  2776  			}
  2777  			v.AuxInt = -1
  2778  		}
  2779  
  2780  	case OpCtz8, OpCtz16, OpCtz32, OpCtz64:
  2781  		// On some architectures, notably amd64, we can generate much better
  2782  		// code for CtzNN if we know that the argument is non-zero.
  2783  		// Capture that information here for use in arch-specific optimizations.
  2784  		x := v.Args[0]
  2785  		lim := ft.limits[x.ID]
  2786  		if lim.umin > 0 || lim.min > 0 || lim.max < 0 {
  2787  			if b.Func.pass.debug > 0 {
  2788  				b.Func.Warnl(v.Pos, "Proved %v non-zero", v.Op)
  2789  			}
  2790  			v.Op = ctzNonZeroOp[v.Op]
  2791  		}
  2792  	case OpRsh8x8, OpRsh8x16, OpRsh8x32, OpRsh8x64,
  2793  		OpRsh16x8, OpRsh16x16, OpRsh16x32, OpRsh16x64,
  2794  		OpRsh32x8, OpRsh32x16, OpRsh32x32, OpRsh32x64,
  2795  		OpRsh64x8, OpRsh64x16, OpRsh64x32, OpRsh64x64:
  2796  		if ft.isNonNegative(v.Args[0]) {
  2797  			if b.Func.pass.debug > 0 {
  2798  				b.Func.Warnl(v.Pos, "Proved %v is unsigned", v.Op)
  2799  			}
  2800  			v.Op = unsignedOp[v.Op]
  2801  		}
  2802  		fallthrough
  2803  	case OpLsh8x8, OpLsh8x16, OpLsh8x32, OpLsh8x64,
  2804  		OpLsh16x8, OpLsh16x16, OpLsh16x32, OpLsh16x64,
  2805  		OpLsh32x8, OpLsh32x16, OpLsh32x32, OpLsh32x64,
  2806  		OpLsh64x8, OpLsh64x16, OpLsh64x32, OpLsh64x64,
  2807  		OpRsh8Ux8, OpRsh8Ux16, OpRsh8Ux32, OpRsh8Ux64,
  2808  		OpRsh16Ux8, OpRsh16Ux16, OpRsh16Ux32, OpRsh16Ux64,
  2809  		OpRsh32Ux8, OpRsh32Ux16, OpRsh32Ux32, OpRsh32Ux64,
  2810  		OpRsh64Ux8, OpRsh64Ux16, OpRsh64Ux32, OpRsh64Ux64:
  2811  		// Check whether, for a << b, we know that b
  2812  		// is strictly less than the number of bits in a.
  2813  		by := v.Args[1]
  2814  		lim := ft.limits[by.ID]
  2815  		bits := 8 * v.Args[0].Type.Size()
  2816  		if lim.umax < uint64(bits) || (lim.max < bits && ft.isNonNegative(by)) {
  2817  			v.AuxInt = 1 // see shiftIsBounded
  2818  			if b.Func.pass.debug > 0 && !by.isGenericIntConst() {
  2819  				b.Func.Warnl(v.Pos, "Proved %v bounded", v.Op)
  2820  			}
  2821  		}
  2822  	case OpDiv8, OpDiv16, OpDiv32, OpDiv64, OpMod8, OpMod16, OpMod32, OpMod64:
  2823  		p, q := ft.limits[v.Args[0].ID], ft.limits[v.Args[1].ID] // p/q
  2824  		if p.nonnegative() && q.nonnegative() {
  2825  			if b.Func.pass.debug > 0 {
  2826  				b.Func.Warnl(v.Pos, "Proved %v is unsigned", v.Op)
  2827  			}
  2828  			v.Op = unsignedOp[v.Op]
  2829  			v.AuxInt = 0
  2830  			break
  2831  		}
  2832  		// Fixup code can be avoided on x86 if we know
  2833  		//  the divisor is not -1 or the dividend > MinIntNN.
  2834  		if v.Op != OpDiv8 && v.Op != OpMod8 && (q.max < -1 || q.min > -1 || p.min > mostNegativeDividend[v.Op]) {
  2835  			// See DivisionNeedsFixUp in rewrite.go.
  2836  			// v.AuxInt = 1 means we have proved that the divisor is not -1
  2837  			// or that the dividend is not the most negative integer,
  2838  			// so we do not need to add fix-up code.
  2839  			if b.Func.pass.debug > 0 {
  2840  				b.Func.Warnl(v.Pos, "Proved %v does not need fix-up", v.Op)
  2841  			}
  2842  			// Only usable on amd64 and 386, and only for ≥ 16-bit ops.
  2843  			// Don't modify AuxInt on other architectures, as that can interfere with CSE.
  2844  			// (Print the debug info above always, so that test/prove.go can be
  2845  			// checked on non-x86 systems.)
  2846  			// TODO: add other architectures?
  2847  			if b.Func.Config.arch == "386" || b.Func.Config.arch == "amd64" {
  2848  				v.AuxInt = 1
  2849  			}
  2850  		}
  2851  	case OpMul64, OpMul32, OpMul16, OpMul8:
  2852  		if vl := ft.limits[v.ID]; vl.min == vl.max || vl.umin == vl.umax {
  2853  			// v is going to be constant folded away; don't "optimize" it.
  2854  			break
  2855  		}
  2856  		x := v.Args[0]
  2857  		xl := ft.limits[x.ID]
  2858  		y := v.Args[1]
  2859  		yl := ft.limits[y.ID]
  2860  		if xl.umin == xl.umax && isPowerOfTwo(xl.umin) ||
  2861  			xl.min == xl.max && isPowerOfTwo(xl.min) ||
  2862  			yl.umin == yl.umax && isPowerOfTwo(yl.umin) ||
  2863  			yl.min == yl.max && isPowerOfTwo(yl.min) {
  2864  			// 0,1 * a power of two is better done as a shift
  2865  			break
  2866  		}
  2867  		switch xOne, yOne := xl.umax <= 1, yl.umax <= 1; {
  2868  		case xOne && yOne:
  2869  			v.Op = bytesizeToAnd[v.Type.Size()]
  2870  			if b.Func.pass.debug > 0 {
  2871  				b.Func.Warnl(v.Pos, "Rewrote Mul %v into And", v)
  2872  			}
  2873  		case yOne && b.Func.Config.haveCondSelect:
  2874  			x, y = y, x
  2875  			fallthrough
  2876  		case xOne && b.Func.Config.haveCondSelect:
  2877  			if !canCondSelect(v, b.Func.Config.arch, nil) {
  2878  				break
  2879  			}
  2880  			zero := b.Func.constVal(bytesizeToConst[v.Type.Size()], v.Type, 0, true)
  2881  			ft.initLimitForNewValue(zero)
  2882  			check := b.NewValue2(v.Pos, bytesizeToNeq[v.Type.Size()], types.Types[types.TBOOL], zero, x)
  2883  			ft.initLimitForNewValue(check)
  2884  			v.reset(OpCondSelect)
  2885  			v.AddArg3(y, zero, check)
  2886  
  2887  			if b.Func.pass.debug > 0 {
  2888  				b.Func.Warnl(v.Pos, "Rewrote Mul %v into CondSelect; %v is bool", v, x)
  2889  			}
  2890  		}
  2891  	case OpEq64, OpEq32, OpEq16, OpEq8,
  2892  		OpNeq64, OpNeq32, OpNeq16, OpNeq8:
  2893  		// Canonicalize:
  2894  		// [0,1] != 1 → [0,1] == 0
  2895  		// [0,1] == 1 → [0,1] != 0
  2896  		// Comparison with zero often encode smaller.
  2897  		xPos, yPos := 0, 1
  2898  		x, y := v.Args[xPos], v.Args[yPos]
  2899  		xl, yl := ft.limits[x.ID], ft.limits[y.ID]
  2900  		xConst, xIsConst := xl.constValue()
  2901  		yConst, yIsConst := yl.constValue()
  2902  		switch {
  2903  		case xIsConst && yIsConst:
  2904  		case xIsConst:
  2905  			xPos, yPos = yPos, xPos
  2906  			x, y = y, x
  2907  			xl, yl = yl, xl
  2908  			xConst, yConst = yConst, xConst
  2909  			fallthrough
  2910  		case yIsConst:
  2911  			if yConst != 1 ||
  2912  				xl.umax > 1 {
  2913  				break
  2914  			}
  2915  			zero := b.Func.constVal(bytesizeToConst[x.Type.Size()], x.Type, 0, true)
  2916  			ft.initLimitForNewValue(zero)
  2917  			oldOp := v.Op
  2918  			v.Op = invertEqNeqOp[v.Op]
  2919  			v.SetArg(yPos, zero)
  2920  			if b.Func.pass.debug > 0 {
  2921  				b.Func.Warnl(v.Pos, "Rewrote %v (%v) %v argument is boolean-like; rewrote to %v against 0", v, oldOp, x, v.Op)
  2922  			}
  2923  		}
  2924  	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
  2925  		x, y := v.Args[0], v.Args[1]
  2926  		xl, yl := ft.limits[x.ID], ft.limits[y.ID]
  2927  		xConst, xIsConst := xl.constValue()
  2928  		yConst, yIsConst := yl.constValue()
  2929  		// Remove no-op Ands
  2930  		switch {
  2931  		case xIsConst && yIsConst:
  2932  		case xIsConst:
  2933  			x, y = y, x
  2934  			xl, yl = yl, xl
  2935  			xConst, yConst = yConst, xConst
  2936  			fallthrough
  2937  		case yIsConst:
  2938  			knownBits, fixedLen := xl.unsignedFixedLeadingBits()
  2939  			varyingLen := 64 - fixedLen
  2940  			wantBits := knownBits | (uint64(1)<<varyingLen - 1)
  2941  			// wantBits has the fixed bits and the worst case bits (set) for the varying bits
  2942  			// if after anding it with y it isn't modified we know the and is always a no-op.
  2943  			if wantBits&uint64(yConst) != wantBits {
  2944  				break
  2945  			}
  2946  
  2947  			oldOp := v.Op
  2948  			v.copyOf(x)
  2949  			if b.Func.pass.debug > 0 {
  2950  				b.Func.Warnl(v.Pos, "Proved %v is a no-op %v", v, oldOp)
  2951  			}
  2952  		}
  2953  	case OpOr64, OpOr32, OpOr16, OpOr8:
  2954  		x, y := v.Args[0], v.Args[1]
  2955  		xl, yl := ft.limits[x.ID], ft.limits[y.ID]
  2956  		xConst, xIsConst := xl.constValue()
  2957  		yConst, yIsConst := yl.constValue()
  2958  		// Remove no-op Ors
  2959  		switch {
  2960  		case xIsConst && yIsConst:
  2961  		case xIsConst:
  2962  			x, y = y, x
  2963  			xl, yl = yl, xl
  2964  			xConst, yConst = yConst, xConst
  2965  			fallthrough
  2966  		case yIsConst:
  2967  			wantBits, _ := xl.unsignedFixedLeadingBits()
  2968  			// wantBits has the fixed bits and the worst case bits (unset) for the varying bits
  2969  			// if after oring it with y it isn't modified we know the or is always a no-op.
  2970  			if wantBits|uint64(yConst) != wantBits {
  2971  				break
  2972  			}
  2973  
  2974  			oldOp := v.Op
  2975  			v.copyOf(x)
  2976  			if b.Func.pass.debug > 0 {
  2977  				b.Func.Warnl(v.Pos, "Proved %v is a no-op %v", v, oldOp)
  2978  			}
  2979  		}
  2980  	}
  2981  }
  2982  
  2983  func (ft *factsTable) constantFoldArguments(v *Value) {
  2984  	for i, arg := range v.Args {
  2985  		lim := ft.limits[arg.ID]
  2986  		constValue, ok := lim.constValue()
  2987  		if !ok {
  2988  			continue
  2989  		}
  2990  		switch arg.Op {
  2991  		case OpConst64, OpConst32, OpConst16, OpConst8, OpConstBool, OpConstNil:
  2992  			continue
  2993  		}
  2994  		typ := arg.Type
  2995  		f := v.Block.Func
  2996  		var c *Value
  2997  		switch {
  2998  		case typ.IsBoolean():
  2999  			c = f.ConstBool(typ, constValue != 0)
  3000  		case typ.IsInteger() && typ.Size() == 1:
  3001  			c = f.ConstInt8(typ, int8(constValue))
  3002  		case typ.IsInteger() && typ.Size() == 2:
  3003  			c = f.ConstInt16(typ, int16(constValue))
  3004  		case typ.IsInteger() && typ.Size() == 4:
  3005  			c = f.ConstInt32(typ, int32(constValue))
  3006  		case typ.IsInteger() && typ.Size() == 8:
  3007  			c = f.ConstInt64(typ, constValue)
  3008  		case typ.IsPtrShaped():
  3009  			if constValue == 0 {
  3010  				c = f.ConstNil(typ)
  3011  			} else {
  3012  				// Not sure how this might happen, but if it
  3013  				// does, just skip it.
  3014  				continue
  3015  			}
  3016  		default:
  3017  			// Not sure how this might happen, but if it
  3018  			// does, just skip it.
  3019  			continue
  3020  		}
  3021  		v.SetArg(i, c)
  3022  		ft.initLimitForNewValue(c)
  3023  		if f.pass.debug > 1 {
  3024  			f.Warnl(v.Pos, "Proved %v's arg %d (%v) is constant %d", v, i, arg, constValue)
  3025  		}
  3026  	}
  3027  }
  3028  
  3029  func (ft *factsTable) simplifyBlock(sdom SparseTree, b *Block) {
  3030  	if b.Kind != block.BlockIf {
  3031  		return
  3032  	}
  3033  
  3034  	// Consider outgoing edges from this block.
  3035  	parent := b
  3036  	for i, branch := range [...]branch{positive, negative} {
  3037  		child := parent.Succs[i].b
  3038  		if getBranch(sdom, parent, child) != unknown {
  3039  			// For edges to uniquely dominated blocks, we
  3040  			// already did this when we visited the child.
  3041  			continue
  3042  		}
  3043  		// For edges to other blocks, this can trim a branch
  3044  		// even if we couldn't get rid of the child itself.
  3045  		ft.checkpoint()
  3046  		addBranchRestrictions(ft, parent, branch)
  3047  		unsat := ft.unsat
  3048  		ft.restore()
  3049  		if unsat {
  3050  			// This branch is impossible, so remove it
  3051  			// from the block.
  3052  			removeBranch(parent, branch)
  3053  			// No point in considering the other branch.
  3054  			// (It *is* possible for both to be
  3055  			// unsatisfiable since the fact table is
  3056  			// incomplete. We could turn this into a
  3057  			// BlockExit, but it doesn't seem worth it.)
  3058  			break
  3059  		}
  3060  	}
  3061  }
  3062  
  3063  func removeBranch(b *Block, branch branch) {
  3064  	c := b.Controls[0]
  3065  	if c != nil && b.Func.pass.debug > 0 {
  3066  		verb := "Proved"
  3067  		if branch == positive {
  3068  			verb = "Disproved"
  3069  		}
  3070  		if b.Func.pass.debug > 1 {
  3071  			b.Func.Warnl(b.Pos, "%s %s (%s)", verb, c.Op, c)
  3072  		} else {
  3073  			b.Func.Warnl(b.Pos, "%s %s", verb, c.Op)
  3074  		}
  3075  	}
  3076  	if c != nil && c.Pos.IsStmt() == src.PosIsStmt && c.Pos.SameFileAndLine(b.Pos) {
  3077  		// attempt to preserve statement marker.
  3078  		b.Pos = b.Pos.WithIsStmt()
  3079  	}
  3080  	if branch == positive || branch == negative {
  3081  		b.Kind = block.BlockFirst
  3082  		b.ResetControls()
  3083  		if branch == positive {
  3084  			b.swapSuccessors()
  3085  		}
  3086  	} else {
  3087  		// TODO: figure out how to remove an entry from a jump table
  3088  	}
  3089  }
  3090  
  3091  // isConstDelta returns non-nil if v is equivalent to w+delta (signed).
  3092  func isConstDelta(v *Value) (w *Value, delta int64) {
  3093  	cop := OpConst64
  3094  	switch v.Op {
  3095  	case OpAdd32, OpSub32:
  3096  		cop = OpConst32
  3097  	case OpAdd16, OpSub16:
  3098  		cop = OpConst16
  3099  	case OpAdd8, OpSub8:
  3100  		cop = OpConst8
  3101  	}
  3102  	switch v.Op {
  3103  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  3104  		if v.Args[0].Op == cop {
  3105  			return v.Args[1], v.Args[0].AuxInt
  3106  		}
  3107  		if v.Args[1].Op == cop {
  3108  			return v.Args[0], v.Args[1].AuxInt
  3109  		}
  3110  	case OpSub64, OpSub32, OpSub16, OpSub8:
  3111  		if v.Args[1].Op == cop {
  3112  			aux := v.Args[1].AuxInt
  3113  			if aux != -aux { // Overflow; too bad
  3114  				return v.Args[0], -aux
  3115  			}
  3116  		}
  3117  	}
  3118  	return nil, 0
  3119  }
  3120  
  3121  // isCleanExt reports whether v is the result of a value-preserving
  3122  // sign or zero extension.
  3123  func isCleanExt(v *Value) bool {
  3124  	switch v.Op {
  3125  	case OpSignExt8to16, OpSignExt8to32, OpSignExt8to64,
  3126  		OpSignExt16to32, OpSignExt16to64, OpSignExt32to64:
  3127  		// signed -> signed is the only value-preserving sign extension
  3128  		return v.Args[0].Type.IsSigned() && v.Type.IsSigned()
  3129  
  3130  	case OpZeroExt8to16, OpZeroExt8to32, OpZeroExt8to64,
  3131  		OpZeroExt16to32, OpZeroExt16to64, OpZeroExt32to64:
  3132  		// unsigned -> signed/unsigned are value-preserving zero extensions
  3133  		return !v.Args[0].Type.IsSigned()
  3134  	}
  3135  	return false
  3136  }
  3137  
  3138  // topoSortValue works with an outside loop to implements an O(V + E) toposort.
  3139  // Practically E = O(1) so it's practically O(V).
  3140  // The algorithm works by maintaining two partitions inside b.Values:
  3141  // the first one is sorted, the second one is unsorted. (spos index the first unsorted value).
  3142  // Then we run DFS on the graph, once we reach a value that has no unsorted dependencies we
  3143  // swap it from the unsorted partition to the end of the sorted partition.
  3144  func topoSortValue(b *Block, positions []uint, spos uint, v *Value) uint {
  3145  	if v.Op == OpPhi {
  3146  		// phis have no dependencies as far as we care, so they are always sorted
  3147  	} else {
  3148  		for _, arg := range v.Args {
  3149  			if arg.Block != b {
  3150  				continue // skip dependencies with other blocks
  3151  			}
  3152  			argIndex := positions[arg.ID]
  3153  			if argIndex < spos {
  3154  				continue // the argument is sorted so skip it
  3155  			}
  3156  			spos = topoSortValue(b, positions, spos, arg)
  3157  		}
  3158  	}
  3159  
  3160  	vpos := positions[v.ID]
  3161  	sv := b.Values[spos]
  3162  
  3163  	b.Values[vpos], b.Values[spos] = sv, v
  3164  	positions[v.ID], positions[sv.ID] = spos, vpos
  3165  
  3166  	return spos + 1
  3167  }
  3168  
  3169  // topoSortValuesInBlock ensure ranging over b.Values visit values before they are being used.
  3170  // It does not consider dependencies with other blocks; thus Phi nodes are considered to not have any dependencies.
  3171  func (ft *factsTable) topoSortValuesInBlock(b *Block) {
  3172  	f := b.Func
  3173  	want := f.NumValues()
  3174  
  3175  	positions := ft.reusedTopoSortIDsToBlockIndexes
  3176  	if want <= cap(positions) {
  3177  		positions = positions[:want]
  3178  	} else {
  3179  		if cap(positions) > 0 {
  3180  			f.Cache.freeUintSlice(positions)
  3181  		}
  3182  		positions = f.Cache.allocUintSlice(want)
  3183  		ft.reusedTopoSortIDsToBlockIndexes = positions
  3184  	}
  3185  
  3186  	for i, v := range b.Values {
  3187  		positions[v.ID] = uint(i)
  3188  	}
  3189  
  3190  	var sorted uint
  3191  	for sorted < uint(len(b.Values)) {
  3192  		sorted = topoSortValue(b, positions, sorted, b.Values[sorted])
  3193  	}
  3194  }
  3195  

View as plain text