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

View as plain text