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

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

View as plain text