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

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

View as plain text