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

View as plain text