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

View as plain text