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

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

View as plain text