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 non-zero number only makes
  2191  	// things smaller. If it's positive or zero, it might
  2192  	// also do nothing (x-0 == v).
  2193  	if yLim.min > 0 {
  2194  		ft.update(v.Block, v, x, signed, lt)
  2195  	} else if yLim.min == 0 {
  2196  		ft.update(v.Block, v, x, signed, lt|eq)
  2197  	}
  2198  
  2199  	// Subtracting a number from a bigger one
  2200  	// can't go below 1. If the numbers might be
  2201  	// equal, then it can't go below 0.
  2202  	if ft.orderS.Ordered(y, x) {
  2203  		ft.signedMin(v, 1)
  2204  	} else if ft.orderS.OrderedOrEqual(y, x) {
  2205  		ft.setNonNegative(v)
  2206  	}
  2207  }
  2208  
  2209  // x%d has been rewritten to x - (x/d)*d.
  2210  func (ft *factsTable) detectMod(v *Value) {
  2211  	var opDiv, opDivU, opMul, opConst Op
  2212  	switch v.Op {
  2213  	case OpSub64:
  2214  		opDiv = OpDiv64
  2215  		opDivU = OpDiv64u
  2216  		opMul = OpMul64
  2217  		opConst = OpConst64
  2218  	case OpSub32:
  2219  		opDiv = OpDiv32
  2220  		opDivU = OpDiv32u
  2221  		opMul = OpMul32
  2222  		opConst = OpConst32
  2223  	case OpSub16:
  2224  		opDiv = OpDiv16
  2225  		opDivU = OpDiv16u
  2226  		opMul = OpMul16
  2227  		opConst = OpConst16
  2228  	case OpSub8:
  2229  		opDiv = OpDiv8
  2230  		opDivU = OpDiv8u
  2231  		opMul = OpMul8
  2232  		opConst = OpConst8
  2233  	}
  2234  
  2235  	mul := v.Args[1]
  2236  	if mul.Op != opMul {
  2237  		return
  2238  	}
  2239  	div, con := mul.Args[0], mul.Args[1]
  2240  	if div.Op == opConst {
  2241  		div, con = con, div
  2242  	}
  2243  	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 {
  2244  		return
  2245  	}
  2246  	ft.modLimit(div.Op == opDiv, v, v.Args[0], con)
  2247  }
  2248  
  2249  // modLimit sets v with facts derived from v = p % q.
  2250  func (ft *factsTable) modLimit(signed bool, v, p, q *Value) {
  2251  	a := ft.limits[p.ID]
  2252  	b := ft.limits[q.ID]
  2253  	if signed {
  2254  		if a.min < 0 && b.min > 0 {
  2255  			ft.signedMinMax(v, -(b.max - 1), b.max-1)
  2256  			return
  2257  		}
  2258  		if !(a.nonnegative() && b.nonnegative()) {
  2259  			// TODO: we could handle signed limits but I didn't bother.
  2260  			return
  2261  		}
  2262  		if a.min >= 0 && b.min > 0 {
  2263  			ft.setNonNegative(v)
  2264  		}
  2265  	}
  2266  	// Underflow in the arithmetic below is ok, it gives to MaxUint64 which does nothing to the limit.
  2267  	ft.unsignedMax(v, min(a.umax, b.umax-1))
  2268  }
  2269  
  2270  // getBranch returns the range restrictions added by p
  2271  // when reaching b. p is the immediate dominator of b.
  2272  func getBranch(sdom SparseTree, p *Block, b *Block) branch {
  2273  	if p == nil {
  2274  		return unknown
  2275  	}
  2276  	switch p.Kind {
  2277  	case BlockIf:
  2278  		// If p and p.Succs[0] are dominators it means that every path
  2279  		// from entry to b passes through p and p.Succs[0]. We care that
  2280  		// no path from entry to b passes through p.Succs[1]. If p.Succs[0]
  2281  		// has one predecessor then (apart from the degenerate case),
  2282  		// there is no path from entry that can reach b through p.Succs[1].
  2283  		// TODO: how about p->yes->b->yes, i.e. a loop in yes.
  2284  		if sdom.IsAncestorEq(p.Succs[0].b, b) && len(p.Succs[0].b.Preds) == 1 {
  2285  			return positive
  2286  		}
  2287  		if sdom.IsAncestorEq(p.Succs[1].b, b) && len(p.Succs[1].b.Preds) == 1 {
  2288  			return negative
  2289  		}
  2290  	case BlockJumpTable:
  2291  		// TODO: this loop can lead to quadratic behavior, as
  2292  		// getBranch can be called len(p.Succs) times.
  2293  		for i, e := range p.Succs {
  2294  			if sdom.IsAncestorEq(e.b, b) && len(e.b.Preds) == 1 {
  2295  				return jumpTable0 + branch(i)
  2296  			}
  2297  		}
  2298  	}
  2299  	return unknown
  2300  }
  2301  
  2302  // addIndVarRestrictions updates the factsTables ft with the facts
  2303  // learned from the induction variable indVar which drives the loop
  2304  // starting in Block b.
  2305  func addIndVarRestrictions(ft *factsTable, b *Block, iv indVar) {
  2306  	d := signed
  2307  	if ft.isNonNegative(iv.min) && ft.isNonNegative(iv.max) {
  2308  		d |= unsigned
  2309  	}
  2310  
  2311  	if iv.flags&indVarMinExc == 0 {
  2312  		addRestrictions(b, ft, d, iv.min, iv.ind, lt|eq)
  2313  	} else {
  2314  		addRestrictions(b, ft, d, iv.min, iv.ind, lt)
  2315  	}
  2316  
  2317  	if iv.flags&indVarMaxInc == 0 {
  2318  		addRestrictions(b, ft, d, iv.ind, iv.max, lt)
  2319  	} else {
  2320  		addRestrictions(b, ft, d, iv.ind, iv.max, lt|eq)
  2321  	}
  2322  }
  2323  
  2324  // addBranchRestrictions updates the factsTables ft with the facts learned when
  2325  // branching from Block b in direction br.
  2326  func addBranchRestrictions(ft *factsTable, b *Block, br branch) {
  2327  	c := b.Controls[0]
  2328  	switch {
  2329  	case br == negative:
  2330  		ft.booleanFalse(c)
  2331  	case br == positive:
  2332  		ft.booleanTrue(c)
  2333  	case br >= jumpTable0:
  2334  		idx := br - jumpTable0
  2335  		val := int64(idx)
  2336  		if v, off := isConstDelta(c); v != nil {
  2337  			// Establish the bound on the underlying value we're switching on,
  2338  			// not on the offset-ed value used as the jump table index.
  2339  			c = v
  2340  			val -= off
  2341  		}
  2342  		ft.newLimit(c, limit{min: val, max: val, umin: uint64(val), umax: uint64(val)})
  2343  	default:
  2344  		panic("unknown branch")
  2345  	}
  2346  }
  2347  
  2348  // addRestrictions updates restrictions from the immediate
  2349  // dominating block (p) using r.
  2350  func addRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r relation) {
  2351  	if t == 0 {
  2352  		// Trivial case: nothing to do.
  2353  		// Should not happen, but just in case.
  2354  		return
  2355  	}
  2356  	for i := domain(1); i <= t; i <<= 1 {
  2357  		if t&i == 0 {
  2358  			continue
  2359  		}
  2360  		ft.update(parent, v, w, i, r)
  2361  	}
  2362  }
  2363  
  2364  func unsignedAddOverflows(a, b uint64, t *types.Type) bool {
  2365  	switch t.Size() {
  2366  	case 8:
  2367  		return a+b < a
  2368  	case 4:
  2369  		return a+b > math.MaxUint32
  2370  	case 2:
  2371  		return a+b > math.MaxUint16
  2372  	case 1:
  2373  		return a+b > math.MaxUint8
  2374  	default:
  2375  		panic("unreachable")
  2376  	}
  2377  }
  2378  
  2379  func signedAddOverflowsOrUnderflows(a, b int64, t *types.Type) bool {
  2380  	r := a + b
  2381  	switch t.Size() {
  2382  	case 8:
  2383  		return (a >= 0 && b >= 0 && r < 0) || (a < 0 && b < 0 && r >= 0)
  2384  	case 4:
  2385  		return r < math.MinInt32 || math.MaxInt32 < r
  2386  	case 2:
  2387  		return r < math.MinInt16 || math.MaxInt16 < r
  2388  	case 1:
  2389  		return r < math.MinInt8 || math.MaxInt8 < r
  2390  	default:
  2391  		panic("unreachable")
  2392  	}
  2393  }
  2394  
  2395  func unsignedSubUnderflows(a, b uint64) bool {
  2396  	return a < b
  2397  }
  2398  
  2399  // checkForChunkedIndexBounds looks for index expressions of the form
  2400  // A[i+delta] where delta < K and i <= len(A)-K.  That is, this is a chunked
  2401  // iteration where the index is not directly compared to the length.
  2402  // if isReslice, then delta can be equal to K.
  2403  func checkForChunkedIndexBounds(ft *factsTable, b *Block, index, bound *Value, isReslice bool) bool {
  2404  	if bound.Op != OpSliceLen && bound.Op != OpStringLen && bound.Op != OpSliceCap {
  2405  		return false
  2406  	}
  2407  
  2408  	// this is a slice bounds check against len or capacity,
  2409  	// and refers back to a prior check against length, which
  2410  	// will also work for the cap since that is not smaller
  2411  	// than the length.
  2412  
  2413  	slice := bound.Args[0]
  2414  	lim := ft.limits[index.ID]
  2415  	if lim.min < 0 {
  2416  		return false
  2417  	}
  2418  	i, delta := isConstDelta(index)
  2419  	if i == nil {
  2420  		return false
  2421  	}
  2422  	if delta < 0 {
  2423  		return false
  2424  	}
  2425  	// special case for blocked iteration over a slice.
  2426  	// slicelen > i + delta && <==== if clauses above
  2427  	// && index >= 0           <==== if clause above
  2428  	// delta >= 0 &&           <==== if clause above
  2429  	// slicelen-K >/>= x       <==== checked below
  2430  	// && K >=/> delta         <==== checked below
  2431  	// then v > w
  2432  	// example: i <=/< len - 4/3 means i+{0,1,2,3} are legal indices
  2433  	for o := ft.orderings[i.ID]; o != nil; o = o.next {
  2434  		if o.d != signed {
  2435  			continue
  2436  		}
  2437  		if ow := o.w; ow.Op == OpAdd64 {
  2438  			var lenOffset *Value
  2439  			if bound := ow.Args[0]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2440  				lenOffset = ow.Args[1]
  2441  			} else if bound := ow.Args[1]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2442  				lenOffset = ow.Args[0]
  2443  			}
  2444  			if lenOffset == nil || lenOffset.Op != OpConst64 {
  2445  				continue
  2446  			}
  2447  			if K := -lenOffset.AuxInt; K >= 0 {
  2448  				or := o.r
  2449  				if isReslice {
  2450  					K++
  2451  				}
  2452  				if or == lt {
  2453  					or = lt | eq
  2454  					K++
  2455  				}
  2456  				if K < 0 { // We hate thinking about overflow
  2457  					continue
  2458  				}
  2459  
  2460  				if delta < K && or == lt|eq {
  2461  					return true
  2462  				}
  2463  			}
  2464  		}
  2465  	}
  2466  	return false
  2467  }
  2468  
  2469  func addLocalFacts(ft *factsTable, b *Block) {
  2470  	ft.topoSortValuesInBlock(b)
  2471  
  2472  	for _, v := range b.Values {
  2473  		// Propagate constant ranges before relative relations to get
  2474  		// the most up-to-date constant bounds for isNonNegative calls.
  2475  		ft.flowLimit(v)
  2476  
  2477  		switch v.Op {
  2478  		case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2479  			x := ft.limits[v.Args[0].ID]
  2480  			y := ft.limits[v.Args[1].ID]
  2481  			if !unsignedAddOverflows(x.umax, y.umax, v.Type) {
  2482  				r := gt
  2483  				if x.maybeZero() {
  2484  					r |= eq
  2485  				}
  2486  				ft.update(b, v, v.Args[1], unsigned, r)
  2487  				r = gt
  2488  				if y.maybeZero() {
  2489  					r |= eq
  2490  				}
  2491  				ft.update(b, v, v.Args[0], unsigned, r)
  2492  			}
  2493  			if x.min >= 0 && !signedAddOverflowsOrUnderflows(x.max, y.max, v.Type) {
  2494  				r := gt
  2495  				if x.maybeZero() {
  2496  					r |= eq
  2497  				}
  2498  				ft.update(b, v, v.Args[1], signed, r)
  2499  			}
  2500  			if y.min >= 0 && !signedAddOverflowsOrUnderflows(x.max, y.max, v.Type) {
  2501  				r := gt
  2502  				if y.maybeZero() {
  2503  					r |= eq
  2504  				}
  2505  				ft.update(b, v, v.Args[0], signed, r)
  2506  			}
  2507  			if x.max <= 0 && !signedAddOverflowsOrUnderflows(x.min, y.min, v.Type) {
  2508  				r := lt
  2509  				if x.maybeZero() {
  2510  					r |= eq
  2511  				}
  2512  				ft.update(b, v, v.Args[1], signed, r)
  2513  			}
  2514  			if y.max <= 0 && !signedAddOverflowsOrUnderflows(x.min, y.min, v.Type) {
  2515  				r := lt
  2516  				if y.maybeZero() {
  2517  					r |= eq
  2518  				}
  2519  				ft.update(b, v, v.Args[0], signed, r)
  2520  			}
  2521  		case OpSub64, OpSub32, OpSub16, OpSub8:
  2522  			x := ft.limits[v.Args[0].ID]
  2523  			y := ft.limits[v.Args[1].ID]
  2524  			if !unsignedSubUnderflows(x.umin, y.umax) {
  2525  				r := lt
  2526  				if y.maybeZero() {
  2527  					r |= eq
  2528  				}
  2529  				ft.update(b, v, v.Args[0], unsigned, r)
  2530  			}
  2531  			// FIXME: we could also do signed facts but the overflow checks are much trickier and I don't need it yet.
  2532  		case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
  2533  			ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2534  			ft.update(b, v, v.Args[1], unsigned, lt|eq)
  2535  			if ft.isNonNegative(v.Args[0]) {
  2536  				ft.update(b, v, v.Args[0], signed, lt|eq)
  2537  			}
  2538  			if ft.isNonNegative(v.Args[1]) {
  2539  				ft.update(b, v, v.Args[1], signed, lt|eq)
  2540  			}
  2541  		case OpOr64, OpOr32, OpOr16, OpOr8:
  2542  			// TODO: investigate how to always add facts without much slowdown, see issue #57959
  2543  			//ft.update(b, v, v.Args[0], unsigned, gt|eq)
  2544  			//ft.update(b, v, v.Args[1], unsigned, gt|eq)
  2545  		case OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  2546  			if !ft.isNonNegative(v.Args[1]) {
  2547  				break
  2548  			}
  2549  			fallthrough
  2550  		case OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8,
  2551  			OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  2552  			OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  2553  			OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8:
  2554  			if !ft.isNonNegative(v.Args[0]) {
  2555  				break
  2556  			}
  2557  			fallthrough
  2558  		case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
  2559  			OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
  2560  			OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  2561  			OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  2562  			OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8:
  2563  			switch add := v.Args[0]; add.Op {
  2564  			// round-up division pattern; given:
  2565  			// v = (x + y) / z
  2566  			// if y < z then v <= x
  2567  			case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2568  				z := v.Args[1]
  2569  				zl := ft.limits[z.ID]
  2570  				var uminDivisor uint64
  2571  				switch v.Op {
  2572  				case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
  2573  					OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  2574  					uminDivisor = zl.umin
  2575  				case OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
  2576  					OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  2577  					OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  2578  					OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8,
  2579  					OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8,
  2580  					OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  2581  					OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  2582  					OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8:
  2583  					uminDivisor = 1 << zl.umin
  2584  				default:
  2585  					panic("unreachable")
  2586  				}
  2587  
  2588  				x := add.Args[0]
  2589  				xl := ft.limits[x.ID]
  2590  				y := add.Args[1]
  2591  				yl := ft.limits[y.ID]
  2592  				if !unsignedAddOverflows(xl.umax, yl.umax, add.Type) {
  2593  					if xl.umax < uminDivisor {
  2594  						ft.update(b, v, y, unsigned, lt|eq)
  2595  					}
  2596  					if yl.umax < uminDivisor {
  2597  						ft.update(b, v, x, unsigned, lt|eq)
  2598  					}
  2599  				}
  2600  			}
  2601  			ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2602  		case OpMod64, OpMod32, OpMod16, OpMod8:
  2603  			if !ft.isNonNegative(v.Args[0]) || !ft.isNonNegative(v.Args[1]) {
  2604  				break
  2605  			}
  2606  			fallthrough
  2607  		case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
  2608  			ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2609  			// Note: we have to be careful that this doesn't imply
  2610  			// that the modulus is >0, which isn't true until *after*
  2611  			// the mod instruction executes (and thus panics if the
  2612  			// modulus is 0). See issue 67625.
  2613  			ft.update(b, v, v.Args[1], unsigned, lt)
  2614  		case OpStringLen:
  2615  			if v.Args[0].Op == OpStringMake {
  2616  				ft.update(b, v, v.Args[0].Args[1], signed, eq)
  2617  			}
  2618  		case OpSliceLen:
  2619  			if v.Args[0].Op == OpSliceMake {
  2620  				ft.update(b, v, v.Args[0].Args[1], signed, eq)
  2621  			}
  2622  		case OpSliceCap:
  2623  			if v.Args[0].Op == OpSliceMake {
  2624  				ft.update(b, v, v.Args[0].Args[2], signed, eq)
  2625  			}
  2626  		case OpIsInBounds:
  2627  			if checkForChunkedIndexBounds(ft, b, v.Args[0], v.Args[1], false) {
  2628  				if b.Func.pass.debug > 0 {
  2629  					b.Func.Warnl(v.Pos, "Proved %s for blocked indexing", v.Op)
  2630  				}
  2631  				ft.booleanTrue(v)
  2632  			}
  2633  		case OpIsSliceInBounds:
  2634  			if checkForChunkedIndexBounds(ft, b, v.Args[0], v.Args[1], true) {
  2635  				if b.Func.pass.debug > 0 {
  2636  					b.Func.Warnl(v.Pos, "Proved %s for blocked reslicing", v.Op)
  2637  				}
  2638  				ft.booleanTrue(v)
  2639  			}
  2640  		case OpPhi:
  2641  			addLocalFactsPhi(ft, v)
  2642  		}
  2643  	}
  2644  }
  2645  
  2646  func addLocalFactsPhi(ft *factsTable, v *Value) {
  2647  	// Look for phis that implement min/max.
  2648  	//   z:
  2649  	//      c = Less64 x y (or other Less/Leq operation)
  2650  	//      If c -> bx by
  2651  	//   bx: <- z
  2652  	//       -> b ...
  2653  	//   by: <- z
  2654  	//      -> b ...
  2655  	//   b: <- bx by
  2656  	//      v = Phi x y
  2657  	// Then v is either min or max of x,y.
  2658  	// If it is the min, then we deduce v <= x && v <= y.
  2659  	// If it is the max, then we deduce v >= x && v >= y.
  2660  	// The min case is useful for the copy builtin, see issue 16833.
  2661  	if len(v.Args) != 2 {
  2662  		return
  2663  	}
  2664  	b := v.Block
  2665  	x := v.Args[0]
  2666  	y := v.Args[1]
  2667  	bx := b.Preds[0].b
  2668  	by := b.Preds[1].b
  2669  	var z *Block // branch point
  2670  	switch {
  2671  	case bx == by: // bx == by == z case
  2672  		z = bx
  2673  	case by.uniquePred() == bx: // bx == z case
  2674  		z = bx
  2675  	case bx.uniquePred() == by: // by == z case
  2676  		z = by
  2677  	case bx.uniquePred() == by.uniquePred():
  2678  		z = bx.uniquePred()
  2679  	}
  2680  	if z == nil || z.Kind != BlockIf {
  2681  		return
  2682  	}
  2683  	c := z.Controls[0]
  2684  	if len(c.Args) != 2 {
  2685  		return
  2686  	}
  2687  	var isMin bool // if c, a less-than comparison, is true, phi chooses x.
  2688  	if bx == z {
  2689  		isMin = b.Preds[0].i == 0
  2690  	} else {
  2691  		isMin = bx.Preds[0].i == 0
  2692  	}
  2693  	if c.Args[0] == x && c.Args[1] == y {
  2694  		// ok
  2695  	} else if c.Args[0] == y && c.Args[1] == x {
  2696  		// Comparison is reversed from how the values are listed in the Phi.
  2697  		isMin = !isMin
  2698  	} else {
  2699  		// Not comparing x and y.
  2700  		return
  2701  	}
  2702  	var dom domain
  2703  	switch c.Op {
  2704  	case OpLess64, OpLess32, OpLess16, OpLess8, OpLeq64, OpLeq32, OpLeq16, OpLeq8:
  2705  		dom = signed
  2706  	case OpLess64U, OpLess32U, OpLess16U, OpLess8U, OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U:
  2707  		dom = unsigned
  2708  	default:
  2709  		return
  2710  	}
  2711  	var rel relation
  2712  	if isMin {
  2713  		rel = lt | eq
  2714  	} else {
  2715  		rel = gt | eq
  2716  	}
  2717  	ft.update(b, v, x, dom, rel)
  2718  	ft.update(b, v, y, dom, rel)
  2719  }
  2720  
  2721  var ctzNonZeroOp = map[Op]Op{
  2722  	OpCtz8:  OpCtz8NonZero,
  2723  	OpCtz16: OpCtz16NonZero,
  2724  	OpCtz32: OpCtz32NonZero,
  2725  	OpCtz64: OpCtz64NonZero,
  2726  }
  2727  var mostNegativeDividend = map[Op]int64{
  2728  	OpDiv16: -1 << 15,
  2729  	OpMod16: -1 << 15,
  2730  	OpDiv32: -1 << 31,
  2731  	OpMod32: -1 << 31,
  2732  	OpDiv64: -1 << 63,
  2733  	OpMod64: -1 << 63,
  2734  }
  2735  var unsignedOp = map[Op]Op{
  2736  	OpDiv8:     OpDiv8u,
  2737  	OpDiv16:    OpDiv16u,
  2738  	OpDiv32:    OpDiv32u,
  2739  	OpDiv64:    OpDiv64u,
  2740  	OpMod8:     OpMod8u,
  2741  	OpMod16:    OpMod16u,
  2742  	OpMod32:    OpMod32u,
  2743  	OpMod64:    OpMod64u,
  2744  	OpRsh8x8:   OpRsh8Ux8,
  2745  	OpRsh8x16:  OpRsh8Ux16,
  2746  	OpRsh8x32:  OpRsh8Ux32,
  2747  	OpRsh8x64:  OpRsh8Ux64,
  2748  	OpRsh16x8:  OpRsh16Ux8,
  2749  	OpRsh16x16: OpRsh16Ux16,
  2750  	OpRsh16x32: OpRsh16Ux32,
  2751  	OpRsh16x64: OpRsh16Ux64,
  2752  	OpRsh32x8:  OpRsh32Ux8,
  2753  	OpRsh32x16: OpRsh32Ux16,
  2754  	OpRsh32x32: OpRsh32Ux32,
  2755  	OpRsh32x64: OpRsh32Ux64,
  2756  	OpRsh64x8:  OpRsh64Ux8,
  2757  	OpRsh64x16: OpRsh64Ux16,
  2758  	OpRsh64x32: OpRsh64Ux32,
  2759  	OpRsh64x64: OpRsh64Ux64,
  2760  }
  2761  
  2762  var bytesizeToConst = [...]Op{
  2763  	8 / 8:  OpConst8,
  2764  	16 / 8: OpConst16,
  2765  	32 / 8: OpConst32,
  2766  	64 / 8: OpConst64,
  2767  }
  2768  var bytesizeToNeq = [...]Op{
  2769  	8 / 8:  OpNeq8,
  2770  	16 / 8: OpNeq16,
  2771  	32 / 8: OpNeq32,
  2772  	64 / 8: OpNeq64,
  2773  }
  2774  var bytesizeToAnd = [...]Op{
  2775  	8 / 8:  OpAnd8,
  2776  	16 / 8: OpAnd16,
  2777  	32 / 8: OpAnd32,
  2778  	64 / 8: OpAnd64,
  2779  }
  2780  
  2781  // simplifyBlock simplifies some constant values in b and evaluates
  2782  // branches to non-uniquely dominated successors of b.
  2783  func simplifyBlock(sdom SparseTree, ft *factsTable, b *Block) {
  2784  	for iv, v := range b.Values {
  2785  		switch v.Op {
  2786  		case OpStaticLECall:
  2787  			if b.Func.pass.debug > 0 && len(v.Args) == 2 {
  2788  				fn := auxToCall(v.Aux).Fn
  2789  				if fn != nil && strings.Contains(fn.String(), "prove") {
  2790  					// Print bounds of any argument to single-arg function with "prove" in name,
  2791  					// for debugging and especially for test/prove.go.
  2792  					// (v.Args[1] is mem).
  2793  					x := v.Args[0]
  2794  					b.Func.Warnl(v.Pos, "Proved %v (%v)", ft.limits[x.ID], x)
  2795  				}
  2796  			}
  2797  		case OpSlicemask:
  2798  			// Replace OpSlicemask operations in b with constants where possible.
  2799  			cap := v.Args[0]
  2800  			x, delta := isConstDelta(cap)
  2801  			if x != nil {
  2802  				// slicemask(x + y)
  2803  				// if x is larger than -y (y is negative), then slicemask is -1.
  2804  				lim := ft.limits[x.ID]
  2805  				if lim.umin > uint64(-delta) {
  2806  					if cap.Op == OpAdd64 {
  2807  						v.reset(OpConst64)
  2808  					} else {
  2809  						v.reset(OpConst32)
  2810  					}
  2811  					if b.Func.pass.debug > 0 {
  2812  						b.Func.Warnl(v.Pos, "Proved slicemask not needed")
  2813  					}
  2814  					v.AuxInt = -1
  2815  				}
  2816  				break
  2817  			}
  2818  			lim := ft.limits[cap.ID]
  2819  			if lim.umin > 0 {
  2820  				if cap.Type.Size() == 8 {
  2821  					v.reset(OpConst64)
  2822  				} else {
  2823  					v.reset(OpConst32)
  2824  				}
  2825  				if b.Func.pass.debug > 0 {
  2826  					b.Func.Warnl(v.Pos, "Proved slicemask not needed (by limit)")
  2827  				}
  2828  				v.AuxInt = -1
  2829  			}
  2830  
  2831  		case OpCtz8, OpCtz16, OpCtz32, OpCtz64:
  2832  			// On some architectures, notably amd64, we can generate much better
  2833  			// code for CtzNN if we know that the argument is non-zero.
  2834  			// Capture that information here for use in arch-specific optimizations.
  2835  			x := v.Args[0]
  2836  			lim := ft.limits[x.ID]
  2837  			if lim.umin > 0 || lim.min > 0 || lim.max < 0 {
  2838  				if b.Func.pass.debug > 0 {
  2839  					b.Func.Warnl(v.Pos, "Proved %v non-zero", v.Op)
  2840  				}
  2841  				v.Op = ctzNonZeroOp[v.Op]
  2842  			}
  2843  		case OpRsh8x8, OpRsh8x16, OpRsh8x32, OpRsh8x64,
  2844  			OpRsh16x8, OpRsh16x16, OpRsh16x32, OpRsh16x64,
  2845  			OpRsh32x8, OpRsh32x16, OpRsh32x32, OpRsh32x64,
  2846  			OpRsh64x8, OpRsh64x16, OpRsh64x32, OpRsh64x64:
  2847  			if ft.isNonNegative(v.Args[0]) {
  2848  				if b.Func.pass.debug > 0 {
  2849  					b.Func.Warnl(v.Pos, "Proved %v is unsigned", v.Op)
  2850  				}
  2851  				v.Op = unsignedOp[v.Op]
  2852  			}
  2853  			fallthrough
  2854  		case OpLsh8x8, OpLsh8x16, OpLsh8x32, OpLsh8x64,
  2855  			OpLsh16x8, OpLsh16x16, OpLsh16x32, OpLsh16x64,
  2856  			OpLsh32x8, OpLsh32x16, OpLsh32x32, OpLsh32x64,
  2857  			OpLsh64x8, OpLsh64x16, OpLsh64x32, OpLsh64x64,
  2858  			OpRsh8Ux8, OpRsh8Ux16, OpRsh8Ux32, OpRsh8Ux64,
  2859  			OpRsh16Ux8, OpRsh16Ux16, OpRsh16Ux32, OpRsh16Ux64,
  2860  			OpRsh32Ux8, OpRsh32Ux16, OpRsh32Ux32, OpRsh32Ux64,
  2861  			OpRsh64Ux8, OpRsh64Ux16, OpRsh64Ux32, OpRsh64Ux64:
  2862  			// Check whether, for a << b, we know that b
  2863  			// is strictly less than the number of bits in a.
  2864  			by := v.Args[1]
  2865  			lim := ft.limits[by.ID]
  2866  			bits := 8 * v.Args[0].Type.Size()
  2867  			if lim.umax < uint64(bits) || (lim.max < bits && ft.isNonNegative(by)) {
  2868  				v.AuxInt = 1 // see shiftIsBounded
  2869  				if b.Func.pass.debug > 0 && !by.isGenericIntConst() {
  2870  					b.Func.Warnl(v.Pos, "Proved %v bounded", v.Op)
  2871  				}
  2872  			}
  2873  		case OpDiv8, OpDiv16, OpDiv32, OpDiv64, OpMod8, OpMod16, OpMod32, OpMod64:
  2874  			p, q := ft.limits[v.Args[0].ID], ft.limits[v.Args[1].ID] // p/q
  2875  			if p.nonnegative() && q.nonnegative() {
  2876  				if b.Func.pass.debug > 0 {
  2877  					b.Func.Warnl(v.Pos, "Proved %v is unsigned", v.Op)
  2878  				}
  2879  				v.Op = unsignedOp[v.Op]
  2880  				v.AuxInt = 0
  2881  				break
  2882  			}
  2883  			// Fixup code can be avoided on x86 if we know
  2884  			//  the divisor is not -1 or the dividend > MinIntNN.
  2885  			if v.Op != OpDiv8 && v.Op != OpMod8 && (q.max < -1 || q.min > -1 || p.min > mostNegativeDividend[v.Op]) {
  2886  				// See DivisionNeedsFixUp in rewrite.go.
  2887  				// v.AuxInt = 1 means we have proved that the divisor is not -1
  2888  				// or that the dividend is not the most negative integer,
  2889  				// so we do not need to add fix-up code.
  2890  				if b.Func.pass.debug > 0 {
  2891  					b.Func.Warnl(v.Pos, "Proved %v does not need fix-up", v.Op)
  2892  				}
  2893  				// Only usable on amd64 and 386, and only for ≥ 16-bit ops.
  2894  				// Don't modify AuxInt on other architectures, as that can interfere with CSE.
  2895  				// (Print the debug info above always, so that test/prove.go can be
  2896  				// checked on non-x86 systems.)
  2897  				// TODO: add other architectures?
  2898  				if b.Func.Config.arch == "386" || b.Func.Config.arch == "amd64" {
  2899  					v.AuxInt = 1
  2900  				}
  2901  			}
  2902  		case OpMul64, OpMul32, OpMul16, OpMul8:
  2903  			if vl := ft.limits[v.ID]; vl.min == vl.max || vl.umin == vl.umax {
  2904  				// v is going to be constant folded away; don't "optimize" it.
  2905  				break
  2906  			}
  2907  			x := v.Args[0]
  2908  			xl := ft.limits[x.ID]
  2909  			y := v.Args[1]
  2910  			yl := ft.limits[y.ID]
  2911  			if xl.umin == xl.umax && isPowerOfTwo(xl.umin) ||
  2912  				xl.min == xl.max && isPowerOfTwo(xl.min) ||
  2913  				yl.umin == yl.umax && isPowerOfTwo(yl.umin) ||
  2914  				yl.min == yl.max && isPowerOfTwo(yl.min) {
  2915  				// 0,1 * a power of two is better done as a shift
  2916  				break
  2917  			}
  2918  			switch xOne, yOne := xl.umax <= 1, yl.umax <= 1; {
  2919  			case xOne && yOne:
  2920  				v.Op = bytesizeToAnd[v.Type.Size()]
  2921  				if b.Func.pass.debug > 0 {
  2922  					b.Func.Warnl(v.Pos, "Rewrote Mul %v into And", v)
  2923  				}
  2924  			case yOne && b.Func.Config.haveCondSelect:
  2925  				x, y = y, x
  2926  				fallthrough
  2927  			case xOne && b.Func.Config.haveCondSelect:
  2928  				if !canCondSelect(v, b.Func.Config.arch, nil) {
  2929  					break
  2930  				}
  2931  				zero := b.Func.constVal(bytesizeToConst[v.Type.Size()], v.Type, 0, true)
  2932  				ft.initLimitForNewValue(zero)
  2933  				check := b.NewValue2(v.Pos, bytesizeToNeq[v.Type.Size()], types.Types[types.TBOOL], zero, x)
  2934  				ft.initLimitForNewValue(check)
  2935  				v.reset(OpCondSelect)
  2936  				v.AddArg3(y, zero, check)
  2937  
  2938  				// FIXME: workaround for go.dev/issues/76060
  2939  				// we need to schedule the Neq before the CondSelect even tho
  2940  				// scheduling is meaningless until we reach the schedule pass.
  2941  				if b.Values[len(b.Values)-1] != check {
  2942  					panic("unreachable; failed sanity check, new value isn't at the end of the block")
  2943  				}
  2944  				b.Values[iv], b.Values[len(b.Values)-1] = b.Values[len(b.Values)-1], b.Values[iv]
  2945  
  2946  				if b.Func.pass.debug > 0 {
  2947  					b.Func.Warnl(v.Pos, "Rewrote Mul %v into CondSelect; %v is bool", v, x)
  2948  				}
  2949  			}
  2950  		}
  2951  
  2952  		// Fold provable constant results.
  2953  		// Helps in cases where we reuse a value after branching on its equality.
  2954  		for i, arg := range v.Args {
  2955  			lim := ft.limits[arg.ID]
  2956  			var constValue int64
  2957  			switch {
  2958  			case lim.min == lim.max:
  2959  				constValue = lim.min
  2960  			case lim.umin == lim.umax:
  2961  				constValue = int64(lim.umin)
  2962  			default:
  2963  				continue
  2964  			}
  2965  			switch arg.Op {
  2966  			case OpConst64, OpConst32, OpConst16, OpConst8, OpConstBool, OpConstNil:
  2967  				continue
  2968  			}
  2969  			typ := arg.Type
  2970  			f := b.Func
  2971  			var c *Value
  2972  			switch {
  2973  			case typ.IsBoolean():
  2974  				c = f.ConstBool(typ, constValue != 0)
  2975  			case typ.IsInteger() && typ.Size() == 1:
  2976  				c = f.ConstInt8(typ, int8(constValue))
  2977  			case typ.IsInteger() && typ.Size() == 2:
  2978  				c = f.ConstInt16(typ, int16(constValue))
  2979  			case typ.IsInteger() && typ.Size() == 4:
  2980  				c = f.ConstInt32(typ, int32(constValue))
  2981  			case typ.IsInteger() && typ.Size() == 8:
  2982  				c = f.ConstInt64(typ, constValue)
  2983  			case typ.IsPtrShaped():
  2984  				if constValue == 0 {
  2985  					c = f.ConstNil(typ)
  2986  				} else {
  2987  					// Not sure how this might happen, but if it
  2988  					// does, just skip it.
  2989  					continue
  2990  				}
  2991  			default:
  2992  				// Not sure how this might happen, but if it
  2993  				// does, just skip it.
  2994  				continue
  2995  			}
  2996  			v.SetArg(i, c)
  2997  			ft.initLimitForNewValue(c)
  2998  			if b.Func.pass.debug > 1 {
  2999  				b.Func.Warnl(v.Pos, "Proved %v's arg %d (%v) is constant %d", v, i, arg, constValue)
  3000  			}
  3001  		}
  3002  	}
  3003  
  3004  	if b.Kind != BlockIf {
  3005  		return
  3006  	}
  3007  
  3008  	// Consider outgoing edges from this block.
  3009  	parent := b
  3010  	for i, branch := range [...]branch{positive, negative} {
  3011  		child := parent.Succs[i].b
  3012  		if getBranch(sdom, parent, child) != unknown {
  3013  			// For edges to uniquely dominated blocks, we
  3014  			// already did this when we visited the child.
  3015  			continue
  3016  		}
  3017  		// For edges to other blocks, this can trim a branch
  3018  		// even if we couldn't get rid of the child itself.
  3019  		ft.checkpoint()
  3020  		addBranchRestrictions(ft, parent, branch)
  3021  		unsat := ft.unsat
  3022  		ft.restore()
  3023  		if unsat {
  3024  			// This branch is impossible, so remove it
  3025  			// from the block.
  3026  			removeBranch(parent, branch)
  3027  			// No point in considering the other branch.
  3028  			// (It *is* possible for both to be
  3029  			// unsatisfiable since the fact table is
  3030  			// incomplete. We could turn this into a
  3031  			// BlockExit, but it doesn't seem worth it.)
  3032  			break
  3033  		}
  3034  	}
  3035  }
  3036  
  3037  func removeBranch(b *Block, branch branch) {
  3038  	c := b.Controls[0]
  3039  	if b.Func.pass.debug > 0 {
  3040  		verb := "Proved"
  3041  		if branch == positive {
  3042  			verb = "Disproved"
  3043  		}
  3044  		if b.Func.pass.debug > 1 {
  3045  			b.Func.Warnl(b.Pos, "%s %s (%s)", verb, c.Op, c)
  3046  		} else {
  3047  			b.Func.Warnl(b.Pos, "%s %s", verb, c.Op)
  3048  		}
  3049  	}
  3050  	if c != nil && c.Pos.IsStmt() == src.PosIsStmt && c.Pos.SameFileAndLine(b.Pos) {
  3051  		// attempt to preserve statement marker.
  3052  		b.Pos = b.Pos.WithIsStmt()
  3053  	}
  3054  	if branch == positive || branch == negative {
  3055  		b.Kind = BlockFirst
  3056  		b.ResetControls()
  3057  		if branch == positive {
  3058  			b.swapSuccessors()
  3059  		}
  3060  	} else {
  3061  		// TODO: figure out how to remove an entry from a jump table
  3062  	}
  3063  }
  3064  
  3065  // isConstDelta returns non-nil if v is equivalent to w+delta (signed).
  3066  func isConstDelta(v *Value) (w *Value, delta int64) {
  3067  	cop := OpConst64
  3068  	switch v.Op {
  3069  	case OpAdd32, OpSub32:
  3070  		cop = OpConst32
  3071  	case OpAdd16, OpSub16:
  3072  		cop = OpConst16
  3073  	case OpAdd8, OpSub8:
  3074  		cop = OpConst8
  3075  	}
  3076  	switch v.Op {
  3077  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  3078  		if v.Args[0].Op == cop {
  3079  			return v.Args[1], v.Args[0].AuxInt
  3080  		}
  3081  		if v.Args[1].Op == cop {
  3082  			return v.Args[0], v.Args[1].AuxInt
  3083  		}
  3084  	case OpSub64, OpSub32, OpSub16, OpSub8:
  3085  		if v.Args[1].Op == cop {
  3086  			aux := v.Args[1].AuxInt
  3087  			if aux != -aux { // Overflow; too bad
  3088  				return v.Args[0], -aux
  3089  			}
  3090  		}
  3091  	}
  3092  	return nil, 0
  3093  }
  3094  
  3095  // isCleanExt reports whether v is the result of a value-preserving
  3096  // sign or zero extension.
  3097  func isCleanExt(v *Value) bool {
  3098  	switch v.Op {
  3099  	case OpSignExt8to16, OpSignExt8to32, OpSignExt8to64,
  3100  		OpSignExt16to32, OpSignExt16to64, OpSignExt32to64:
  3101  		// signed -> signed is the only value-preserving sign extension
  3102  		return v.Args[0].Type.IsSigned() && v.Type.IsSigned()
  3103  
  3104  	case OpZeroExt8to16, OpZeroExt8to32, OpZeroExt8to64,
  3105  		OpZeroExt16to32, OpZeroExt16to64, OpZeroExt32to64:
  3106  		// unsigned -> signed/unsigned are value-preserving zero extensions
  3107  		return !v.Args[0].Type.IsSigned()
  3108  	}
  3109  	return false
  3110  }
  3111  
  3112  func getDependencyScore(scores []uint, v *Value) (score uint) {
  3113  	if score = scores[v.ID]; score != 0 {
  3114  		return score
  3115  	}
  3116  	defer func() {
  3117  		scores[v.ID] = score
  3118  	}()
  3119  	if v.Op == OpPhi {
  3120  		return 1
  3121  	}
  3122  	score = 2 // NIT(@Jorropo): always order phis first to make GOSSAFUNC pretty.
  3123  	for _, a := range v.Args {
  3124  		if a.Block != v.Block {
  3125  			continue
  3126  		}
  3127  		score = max(score, getDependencyScore(scores, a)+1)
  3128  	}
  3129  	return score
  3130  }
  3131  
  3132  // topoSortValuesInBlock ensure ranging over b.Values visit values before they are being used.
  3133  // It does not consider dependencies with other blocks; thus Phi nodes are considered to not have any dependecies.
  3134  // The result is always determistic and does not depend on the previous slice ordering.
  3135  func (ft *factsTable) topoSortValuesInBlock(b *Block) {
  3136  	f := b.Func
  3137  	want := f.NumValues()
  3138  
  3139  	scores := ft.reusedTopoSortScoresTable
  3140  	if want <= cap(scores) {
  3141  		scores = scores[:want]
  3142  	} else {
  3143  		if cap(scores) > 0 {
  3144  			f.Cache.freeUintSlice(scores)
  3145  		}
  3146  		scores = f.Cache.allocUintSlice(want)
  3147  		ft.reusedTopoSortScoresTable = scores
  3148  	}
  3149  
  3150  	for _, v := range b.Values {
  3151  		scores[v.ID] = 0 // sentinel
  3152  	}
  3153  
  3154  	slices.SortFunc(b.Values, func(a, b *Value) int {
  3155  		dependencyScoreA := getDependencyScore(scores, a)
  3156  		dependencyScoreB := getDependencyScore(scores, b)
  3157  		if dependencyScoreA != dependencyScoreB {
  3158  			return cmp.Compare(dependencyScoreA, dependencyScoreB)
  3159  		}
  3160  		return cmp.Compare(a.ID, b.ID)
  3161  	})
  3162  }
  3163  

View as plain text