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. Currently, findIndVars
  1566  	// is limited to one induction variable per block.
  1567  	var indVars map[*Block]indVar
  1568  	for _, v := range findIndVar(f) {
  1569  		ind := v.ind
  1570  		if len(ind.Args) != 2 {
  1571  			// the rewrite code assumes there is only ever two parents to loops
  1572  			panic("unexpected induction with too many parents")
  1573  		}
  1574  
  1575  		nxt := v.nxt
  1576  		if !(ind.Uses == 2 && // 2 used by comparison and next
  1577  			nxt.Uses == 1) { // 1 used by induction
  1578  			// ind or nxt is used inside the loop, add it for the facts table
  1579  			if indVars == nil {
  1580  				indVars = make(map[*Block]indVar)
  1581  			}
  1582  			indVars[v.entry] = v
  1583  			continue
  1584  		} else {
  1585  			// Since this induction variable is not used for anything but counting the iterations,
  1586  			// no point in putting it into the facts table.
  1587  		}
  1588  
  1589  		maybeRewriteLoopToDownwardCountingLoop(f, v)
  1590  	}
  1591  
  1592  	ft := newFactsTable(f)
  1593  	ft.checkpoint()
  1594  
  1595  	// Find length and capacity ops.
  1596  	for _, b := range f.Blocks {
  1597  		for _, v := range b.Values {
  1598  			if v.Uses == 0 {
  1599  				// We don't care about dead values.
  1600  				// (There can be some that are CSEd but not removed yet.)
  1601  				continue
  1602  			}
  1603  			switch v.Op {
  1604  			case OpSliceLen:
  1605  				if ft.lens == nil {
  1606  					ft.lens = map[ID]*Value{}
  1607  				}
  1608  				// Set all len Values for the same slice as equal in the poset.
  1609  				// The poset handles transitive relations, so Values related to
  1610  				// any OpSliceLen for this slice will be correctly related to others.
  1611  				if l, ok := ft.lens[v.Args[0].ID]; ok {
  1612  					ft.update(b, v, l, signed, eq)
  1613  				} else {
  1614  					ft.lens[v.Args[0].ID] = v
  1615  				}
  1616  			case OpSliceCap:
  1617  				if ft.caps == nil {
  1618  					ft.caps = map[ID]*Value{}
  1619  				}
  1620  				// Same as case OpSliceLen above, but for slice cap.
  1621  				if c, ok := ft.caps[v.Args[0].ID]; ok {
  1622  					ft.update(b, v, c, signed, eq)
  1623  				} else {
  1624  					ft.caps[v.Args[0].ID] = v
  1625  				}
  1626  			}
  1627  		}
  1628  	}
  1629  
  1630  	// current node state
  1631  	type walkState int
  1632  	const (
  1633  		descend walkState = iota
  1634  		simplify
  1635  	)
  1636  	// work maintains the DFS stack.
  1637  	type bp struct {
  1638  		block *Block    // current handled block
  1639  		state walkState // what's to do
  1640  	}
  1641  	work := make([]bp, 0, 256)
  1642  	work = append(work, bp{
  1643  		block: f.Entry,
  1644  		state: descend,
  1645  	})
  1646  
  1647  	idom := f.Idom()
  1648  	sdom := f.Sdom()
  1649  
  1650  	// DFS on the dominator tree.
  1651  	//
  1652  	// For efficiency, we consider only the dominator tree rather
  1653  	// than the entire flow graph. On the way down, we consider
  1654  	// incoming branches and accumulate conditions that uniquely
  1655  	// dominate the current block. If we discover a contradiction,
  1656  	// we can eliminate the entire block and all of its children.
  1657  	// On the way back up, we consider outgoing branches that
  1658  	// haven't already been considered. This way we consider each
  1659  	// branch condition only once.
  1660  	for len(work) > 0 {
  1661  		node := work[len(work)-1]
  1662  		work = work[:len(work)-1]
  1663  		parent := idom[node.block.ID]
  1664  		branch := getBranch(sdom, parent, node.block)
  1665  
  1666  		switch node.state {
  1667  		case descend:
  1668  			ft.checkpoint()
  1669  
  1670  			// Entering the block, add facts about the induction variable
  1671  			// that is bound to this block.
  1672  			if iv, ok := indVars[node.block]; ok {
  1673  				addIndVarRestrictions(ft, parent, iv)
  1674  			}
  1675  
  1676  			// Add results of reaching this block via a branch from
  1677  			// its immediate dominator (if any).
  1678  			if branch != unknown {
  1679  				addBranchRestrictions(ft, parent, branch)
  1680  			}
  1681  
  1682  			// Add slices of the same length start from current block.
  1683  			addSlicesOfSameLen(ft, node.block)
  1684  
  1685  			if ft.unsat {
  1686  				// node.block is unreachable.
  1687  				// Remove it and don't visit
  1688  				// its children.
  1689  				removeBranch(parent, branch)
  1690  				ft.restore()
  1691  				break
  1692  			}
  1693  			// Otherwise, we can now commit to
  1694  			// taking this branch. We'll restore
  1695  			// ft when we unwind.
  1696  
  1697  			// Add facts about the values in the current block.
  1698  			addLocalFacts(ft, node.block)
  1699  
  1700  			work = append(work, bp{
  1701  				block: node.block,
  1702  				state: simplify,
  1703  			})
  1704  			for s := sdom.Child(node.block); s != nil; s = sdom.Sibling(s) {
  1705  				work = append(work, bp{
  1706  					block: s,
  1707  					state: descend,
  1708  				})
  1709  			}
  1710  
  1711  		case simplify:
  1712  			simplifyBlock(sdom, ft, node.block)
  1713  			ft.restore()
  1714  		}
  1715  	}
  1716  
  1717  	ft.restore()
  1718  
  1719  	ft.cleanup(f)
  1720  }
  1721  
  1722  // initLimit sets initial constant limit for v.  This limit is based
  1723  // only on the operation itself, not any of its input arguments. This
  1724  // method is only used in two places, once when the prove pass startup
  1725  // and the other when a new ssa value is created, both for init. (unlike
  1726  // flowLimit, below, which computes additional constraints based on
  1727  // ranges of opcode arguments).
  1728  func initLimit(v *Value) limit {
  1729  	if v.Type.IsBoolean() {
  1730  		switch v.Op {
  1731  		case OpConstBool:
  1732  			b := v.AuxInt
  1733  			return limit{min: b, max: b, umin: uint64(b), umax: uint64(b)}
  1734  		default:
  1735  			return limit{min: 0, max: 1, umin: 0, umax: 1}
  1736  		}
  1737  	}
  1738  	if v.Type.IsPtrShaped() { // These are the types that EqPtr/NeqPtr operate on, except uintptr.
  1739  		switch v.Op {
  1740  		case OpConstNil:
  1741  			return limit{min: 0, max: 0, umin: 0, umax: 0}
  1742  		case OpAddr, OpLocalAddr: // TODO: others?
  1743  			l := noLimit()
  1744  			l.umin = 1
  1745  			return l
  1746  		default:
  1747  			return noLimit()
  1748  		}
  1749  	}
  1750  	if !v.Type.IsInteger() {
  1751  		return noLimit()
  1752  	}
  1753  
  1754  	// Default limits based on type.
  1755  	lim := noLimitForBitsize(uint(v.Type.Size()) * 8)
  1756  
  1757  	// Tighter limits on some opcodes.
  1758  	switch v.Op {
  1759  	// constants
  1760  	case OpConst64:
  1761  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(v.AuxInt), umax: uint64(v.AuxInt)}
  1762  	case OpConst32:
  1763  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint32(v.AuxInt)), umax: uint64(uint32(v.AuxInt))}
  1764  	case OpConst16:
  1765  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint16(v.AuxInt)), umax: uint64(uint16(v.AuxInt))}
  1766  	case OpConst8:
  1767  		lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint8(v.AuxInt)), umax: uint64(uint8(v.AuxInt))}
  1768  
  1769  	// extensions
  1770  	case OpZeroExt8to64, OpZeroExt8to32, OpZeroExt8to16:
  1771  		lim = lim.signedMinMax(0, 1<<8-1)
  1772  		lim = lim.unsignedMax(1<<8 - 1)
  1773  	case OpZeroExt16to64, OpZeroExt16to32:
  1774  		lim = lim.signedMinMax(0, 1<<16-1)
  1775  		lim = lim.unsignedMax(1<<16 - 1)
  1776  	case OpZeroExt32to64:
  1777  		lim = lim.signedMinMax(0, 1<<32-1)
  1778  		lim = lim.unsignedMax(1<<32 - 1)
  1779  	case OpSignExt8to64, OpSignExt8to32, OpSignExt8to16:
  1780  		lim = lim.signedMinMax(math.MinInt8, math.MaxInt8)
  1781  	case OpSignExt16to64, OpSignExt16to32:
  1782  		lim = lim.signedMinMax(math.MinInt16, math.MaxInt16)
  1783  	case OpSignExt32to64:
  1784  		lim = lim.signedMinMax(math.MinInt32, math.MaxInt32)
  1785  
  1786  	// math/bits intrinsics
  1787  	case OpCtz64, OpBitLen64, OpPopCount64,
  1788  		OpCtz32, OpBitLen32, OpPopCount32,
  1789  		OpCtz16, OpBitLen16, OpPopCount16,
  1790  		OpCtz8, OpBitLen8, OpPopCount8:
  1791  		lim = lim.unsignedMax(uint64(v.Args[0].Type.Size() * 8))
  1792  
  1793  	// bool to uint8 conversion
  1794  	case OpCvtBoolToUint8:
  1795  		lim = lim.unsignedMax(1)
  1796  
  1797  	// length operations
  1798  	case OpSliceLen, OpSliceCap:
  1799  		f := v.Block.Func
  1800  		elemSize := uint64(v.Args[0].Type.Elem().Size())
  1801  		if elemSize > 0 {
  1802  			heapSize := uint64(1)<<(uint64(f.Config.PtrSize)*8) - 1
  1803  			maximumElementsFittingInHeap := heapSize / elemSize
  1804  			lim = lim.unsignedMax(maximumElementsFittingInHeap)
  1805  		}
  1806  		fallthrough
  1807  	case OpStringLen:
  1808  		lim = lim.signedMin(0)
  1809  	}
  1810  
  1811  	// signed <-> unsigned propagation
  1812  	if lim.min >= 0 {
  1813  		lim = lim.unsignedMinMax(uint64(lim.min), uint64(lim.max))
  1814  	}
  1815  	if fitsInBitsU(lim.umax, uint(8*v.Type.Size()-1)) {
  1816  		lim = lim.signedMinMax(int64(lim.umin), int64(lim.umax))
  1817  	}
  1818  
  1819  	return lim
  1820  }
  1821  
  1822  // flowLimit updates the known limits of v in ft.
  1823  // flowLimit can use the ranges of input arguments.
  1824  //
  1825  // Note: this calculation only happens at the point the value is defined. We do not reevaluate
  1826  // it later. So for example:
  1827  //
  1828  //	v := x + y
  1829  //	if 0 <= x && x < 5 && 0 <= y && y < 5 { ... use v ... }
  1830  //
  1831  // we don't discover that the range of v is bounded in the conditioned
  1832  // block. We could recompute the range of v once we enter the block so
  1833  // we know that it is 0 <= v <= 8, but we don't have a mechanism to do
  1834  // that right now.
  1835  func (ft *factsTable) flowLimit(v *Value) {
  1836  	if !v.Type.IsInteger() {
  1837  		// TODO: boolean?
  1838  		return
  1839  	}
  1840  
  1841  	// Additional limits based on opcode and argument.
  1842  	// No need to repeat things here already done in initLimit.
  1843  	switch v.Op {
  1844  
  1845  	// extensions
  1846  	case OpZeroExt8to64, OpZeroExt8to32, OpZeroExt8to16, OpZeroExt16to64, OpZeroExt16to32, OpZeroExt32to64:
  1847  		a := ft.limits[v.Args[0].ID]
  1848  		ft.unsignedMinMax(v, a.umin, a.umax)
  1849  	case OpSignExt8to64, OpSignExt8to32, OpSignExt8to16, OpSignExt16to64, OpSignExt16to32, OpSignExt32to64:
  1850  		a := ft.limits[v.Args[0].ID]
  1851  		ft.signedMinMax(v, a.min, a.max)
  1852  	case OpTrunc64to8, OpTrunc64to16, OpTrunc64to32, OpTrunc32to8, OpTrunc32to16, OpTrunc16to8:
  1853  		a := ft.limits[v.Args[0].ID]
  1854  		if a.umax <= 1<<(uint64(v.Type.Size())*8)-1 {
  1855  			ft.unsignedMinMax(v, a.umin, a.umax)
  1856  		}
  1857  
  1858  	// math/bits
  1859  	case OpCtz64, OpCtz32, OpCtz16, OpCtz8:
  1860  		a := v.Args[0]
  1861  		al := ft.limits[a.ID]
  1862  		ft.newLimit(v, al.ctz(uint(a.Type.Size())*8))
  1863  
  1864  	case OpPopCount64, OpPopCount32, OpPopCount16, OpPopCount8:
  1865  		a := v.Args[0]
  1866  		al := ft.limits[a.ID]
  1867  		ft.newLimit(v, al.popcount(uint(a.Type.Size())*8))
  1868  
  1869  	case OpBitLen64, OpBitLen32, OpBitLen16, OpBitLen8:
  1870  		a := v.Args[0]
  1871  		al := ft.limits[a.ID]
  1872  		ft.newLimit(v, al.bitlen(uint(a.Type.Size())*8))
  1873  
  1874  	// Masks.
  1875  
  1876  	// TODO: if y.umax and y.umin share a leading bit pattern, y also has that leading bit pattern.
  1877  	// we could compare the patterns of always set bits in a and b and learn more about minimum and maximum.
  1878  	// But I doubt this help any real world code.
  1879  	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
  1880  		// AND can only make the value smaller.
  1881  		a := ft.limits[v.Args[0].ID]
  1882  		b := ft.limits[v.Args[1].ID]
  1883  		ft.unsignedMax(v, min(a.umax, b.umax))
  1884  	case OpOr64, OpOr32, OpOr16, OpOr8:
  1885  		// OR can only make the value bigger and can't flip bits proved to be zero in both inputs.
  1886  		a := ft.limits[v.Args[0].ID]
  1887  		b := ft.limits[v.Args[1].ID]
  1888  		ft.unsignedMinMax(v,
  1889  			max(a.umin, b.umin),
  1890  			1<<bits.Len64(a.umax|b.umax)-1)
  1891  	case OpXor64, OpXor32, OpXor16, OpXor8:
  1892  		// XOR can't flip bits that are proved to be zero in both inputs.
  1893  		a := ft.limits[v.Args[0].ID]
  1894  		b := ft.limits[v.Args[1].ID]
  1895  		ft.unsignedMax(v, 1<<bits.Len64(a.umax|b.umax)-1)
  1896  	case OpCom64, OpCom32, OpCom16, OpCom8:
  1897  		a := ft.limits[v.Args[0].ID]
  1898  		ft.newLimit(v, a.com(uint(v.Type.Size())*8))
  1899  
  1900  	// Arithmetic.
  1901  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  1902  		a := ft.limits[v.Args[0].ID]
  1903  		b := ft.limits[v.Args[1].ID]
  1904  		ft.newLimit(v, a.add(b, uint(v.Type.Size())*8))
  1905  	case OpSub64, OpSub32, OpSub16, OpSub8:
  1906  		a := ft.limits[v.Args[0].ID]
  1907  		b := ft.limits[v.Args[1].ID]
  1908  		ft.newLimit(v, a.sub(b, uint(v.Type.Size())*8))
  1909  		ft.detectMod(v)
  1910  		ft.detectSliceLenRelation(v)
  1911  		ft.detectSubRelations(v)
  1912  	case OpNeg64, OpNeg32, OpNeg16, OpNeg8:
  1913  		a := ft.limits[v.Args[0].ID]
  1914  		bitsize := uint(v.Type.Size()) * 8
  1915  		ft.newLimit(v, a.neg(bitsize))
  1916  	case OpMul64, OpMul32, OpMul16, OpMul8:
  1917  		a := ft.limits[v.Args[0].ID]
  1918  		b := ft.limits[v.Args[1].ID]
  1919  		ft.newLimit(v, a.mul(b, uint(v.Type.Size())*8))
  1920  	case OpLsh64x64, OpLsh64x32, OpLsh64x16, OpLsh64x8,
  1921  		OpLsh32x64, OpLsh32x32, OpLsh32x16, OpLsh32x8,
  1922  		OpLsh16x64, OpLsh16x32, OpLsh16x16, OpLsh16x8,
  1923  		OpLsh8x64, OpLsh8x32, OpLsh8x16, OpLsh8x8:
  1924  		a := ft.limits[v.Args[0].ID]
  1925  		b := ft.limits[v.Args[1].ID]
  1926  		bitsize := uint(v.Type.Size()) * 8
  1927  		ft.newLimit(v, a.mul(b.exp2(bitsize), bitsize))
  1928  	case OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8,
  1929  		OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  1930  		OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  1931  		OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8:
  1932  		a := ft.limits[v.Args[0].ID]
  1933  		b := ft.limits[v.Args[1].ID]
  1934  		if b.min >= 0 {
  1935  			// Shift of negative makes a value closer to 0 (greater),
  1936  			// so if a.min is negative, v.min is a.min>>b.min instead of a.min>>b.max,
  1937  			// and similarly if a.max is negative, v.max is a.max>>b.max.
  1938  			// Easier to compute min and max of both than to write sign logic.
  1939  			vmin := min(a.min>>b.min, a.min>>b.max)
  1940  			vmax := max(a.max>>b.min, a.max>>b.max)
  1941  			ft.signedMinMax(v, vmin, vmax)
  1942  		}
  1943  	case OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8,
  1944  		OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  1945  		OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  1946  		OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8:
  1947  		a := ft.limits[v.Args[0].ID]
  1948  		b := ft.limits[v.Args[1].ID]
  1949  		if b.min >= 0 {
  1950  			ft.unsignedMinMax(v, a.umin>>b.max, a.umax>>b.min)
  1951  		}
  1952  	case OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  1953  		a := ft.limits[v.Args[0].ID]
  1954  		b := ft.limits[v.Args[1].ID]
  1955  		if !(a.nonnegative() && b.nonnegative()) {
  1956  			// TODO: we could handle signed limits but I didn't bother.
  1957  			break
  1958  		}
  1959  		fallthrough
  1960  	case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u:
  1961  		a := ft.limits[v.Args[0].ID]
  1962  		b := ft.limits[v.Args[1].ID]
  1963  		lim := noLimit()
  1964  		if b.umax > 0 {
  1965  			lim = lim.unsignedMin(a.umin / b.umax)
  1966  		}
  1967  		if b.umin > 0 {
  1968  			lim = lim.unsignedMax(a.umax / b.umin)
  1969  		}
  1970  		ft.newLimit(v, lim)
  1971  	case OpMod64, OpMod32, OpMod16, OpMod8:
  1972  		ft.modLimit(true, v, v.Args[0], v.Args[1])
  1973  	case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
  1974  		ft.modLimit(false, v, v.Args[0], v.Args[1])
  1975  
  1976  	case OpPhi:
  1977  		// Compute the union of all the input phis.
  1978  		// Often this will convey no information, because the block
  1979  		// is not dominated by its predecessors and hence the
  1980  		// phi arguments might not have been processed yet. But if
  1981  		// the values are declared earlier, it may help. e.g., for
  1982  		//    v = phi(c3, c5)
  1983  		// where c3 = OpConst [3] and c5 = OpConst [5] are
  1984  		// defined in the entry block, we can derive [3,5]
  1985  		// as the limit for v.
  1986  		l := ft.limits[v.Args[0].ID]
  1987  		for _, a := range v.Args[1:] {
  1988  			l2 := ft.limits[a.ID]
  1989  			l.min = min(l.min, l2.min)
  1990  			l.max = max(l.max, l2.max)
  1991  			l.umin = min(l.umin, l2.umin)
  1992  			l.umax = max(l.umax, l2.umax)
  1993  		}
  1994  		ft.newLimit(v, l)
  1995  	}
  1996  }
  1997  
  1998  // detectSliceLenRelation matches the pattern where
  1999  //  1. v := slicelen - index, OR v := slicecap - index
  2000  //     AND
  2001  //  2. index <= slicelen - K
  2002  //     THEN
  2003  //
  2004  // slicecap - index >= slicelen - index >= K
  2005  //
  2006  // Note that "index" is not used for indexing in this pattern, but
  2007  // in the motivating example (chunked slice iteration) it is.
  2008  func (ft *factsTable) detectSliceLenRelation(v *Value) {
  2009  	if v.Op != OpSub64 {
  2010  		return
  2011  	}
  2012  
  2013  	if !(v.Args[0].Op == OpSliceLen || v.Args[0].Op == OpStringLen || v.Args[0].Op == OpSliceCap) {
  2014  		return
  2015  	}
  2016  
  2017  	index := v.Args[1]
  2018  	if !ft.isNonNegative(index) {
  2019  		return
  2020  	}
  2021  	slice := v.Args[0].Args[0]
  2022  
  2023  	for o := ft.orderings[index.ID]; o != nil; o = o.next {
  2024  		if o.d != signed {
  2025  			continue
  2026  		}
  2027  		or := o.r
  2028  		if or != lt && or != lt|eq {
  2029  			continue
  2030  		}
  2031  		ow := o.w
  2032  		if ow.Op != OpAdd64 && ow.Op != OpSub64 {
  2033  			continue
  2034  		}
  2035  		var lenOffset *Value
  2036  		if bound := ow.Args[0]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2037  			lenOffset = ow.Args[1]
  2038  		} else if bound := ow.Args[1]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2039  			// Do not infer K - slicelen, see issue #76709.
  2040  			if ow.Op == OpAdd64 {
  2041  				lenOffset = ow.Args[0]
  2042  			}
  2043  		}
  2044  		if lenOffset == nil || lenOffset.Op != OpConst64 {
  2045  			continue
  2046  		}
  2047  		K := lenOffset.AuxInt
  2048  		if ow.Op == OpAdd64 {
  2049  			K = -K
  2050  		}
  2051  		if K < 0 {
  2052  			continue
  2053  		}
  2054  		if or == lt {
  2055  			K++
  2056  		}
  2057  		if K < 0 { // We hate thinking about overflow
  2058  			continue
  2059  		}
  2060  		ft.signedMin(v, K)
  2061  	}
  2062  }
  2063  
  2064  // v must be Sub{64,32,16,8}.
  2065  func (ft *factsTable) detectSubRelations(v *Value) {
  2066  	// v = x-y
  2067  	x := v.Args[0]
  2068  	y := v.Args[1]
  2069  	if x == y {
  2070  		ft.signedMinMax(v, 0, 0)
  2071  		return
  2072  	}
  2073  	xLim := ft.limits[x.ID]
  2074  	yLim := ft.limits[y.ID]
  2075  
  2076  	// Check if we might wrap around. If so, give up.
  2077  	width := uint(v.Type.Size()) * 8
  2078  
  2079  	// v >= 1 in the signed domain?
  2080  	var vSignedMinOne bool
  2081  
  2082  	// Signed optimizations
  2083  	if _, ok := safeSub(xLim.min, yLim.max, width); ok {
  2084  		// Large abs negative y can also overflow
  2085  		if _, ok := safeSub(xLim.max, yLim.min, width); ok {
  2086  			// x-y won't overflow
  2087  
  2088  			// Subtracting a positive non-zero number only makes
  2089  			// things smaller. If it's positive or zero, it might
  2090  			// also do nothing (x-0 == v).
  2091  			if yLim.min > 0 {
  2092  				ft.update(v.Block, v, x, signed, lt)
  2093  			} else if yLim.min == 0 {
  2094  				ft.update(v.Block, v, x, signed, lt|eq)
  2095  			}
  2096  
  2097  			// Subtracting a number from a bigger one
  2098  			// can't go below 1. If the numbers might be
  2099  			// equal, then it can't go below 0.
  2100  			//
  2101  			// This requires the overflow checks because
  2102  			// large negative y can cause an overflow.
  2103  			if ft.orderS.Ordered(y, x) {
  2104  				ft.signedMin(v, 1)
  2105  				vSignedMinOne = true
  2106  			} else if ft.orderS.OrderedOrEqual(y, x) {
  2107  				ft.setNonNegative(v)
  2108  			}
  2109  		}
  2110  	}
  2111  
  2112  	// Unsigned optimizations
  2113  	if _, ok := safeSubU(xLim.umin, yLim.umax, width); ok {
  2114  		if yLim.umin > 0 {
  2115  			ft.update(v.Block, v, x, unsigned, lt)
  2116  		} else {
  2117  			ft.update(v.Block, v, x, unsigned, lt|eq)
  2118  		}
  2119  	}
  2120  
  2121  	// Proving v >= 1 in the signed domain automatically
  2122  	// proves it in the unsigned domain, so we can skip it.
  2123  	//
  2124  	// We don't need overflow checks here, since if y < x,
  2125  	// then x-y can never overflow for uint.
  2126  	if !vSignedMinOne && ft.orderU.Ordered(y, x) {
  2127  		ft.unsignedMin(v, 1)
  2128  	}
  2129  }
  2130  
  2131  // x%d has been rewritten to x - (x/d)*d.
  2132  func (ft *factsTable) detectMod(v *Value) {
  2133  	var opDiv, opDivU, opMul, opConst Op
  2134  	switch v.Op {
  2135  	case OpSub64:
  2136  		opDiv = OpDiv64
  2137  		opDivU = OpDiv64u
  2138  		opMul = OpMul64
  2139  		opConst = OpConst64
  2140  	case OpSub32:
  2141  		opDiv = OpDiv32
  2142  		opDivU = OpDiv32u
  2143  		opMul = OpMul32
  2144  		opConst = OpConst32
  2145  	case OpSub16:
  2146  		opDiv = OpDiv16
  2147  		opDivU = OpDiv16u
  2148  		opMul = OpMul16
  2149  		opConst = OpConst16
  2150  	case OpSub8:
  2151  		opDiv = OpDiv8
  2152  		opDivU = OpDiv8u
  2153  		opMul = OpMul8
  2154  		opConst = OpConst8
  2155  	}
  2156  
  2157  	mul := v.Args[1]
  2158  	if mul.Op != opMul {
  2159  		return
  2160  	}
  2161  	div, con := mul.Args[0], mul.Args[1]
  2162  	if div.Op == opConst {
  2163  		div, con = con, div
  2164  	}
  2165  	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 {
  2166  		return
  2167  	}
  2168  	ft.modLimit(div.Op == opDiv, v, v.Args[0], con)
  2169  }
  2170  
  2171  // modLimit sets v with facts derived from v = p % q.
  2172  func (ft *factsTable) modLimit(signed bool, v, p, q *Value) {
  2173  	a := ft.limits[p.ID]
  2174  	b := ft.limits[q.ID]
  2175  	if signed {
  2176  		if a.min < 0 && b.min > 0 {
  2177  			ft.signedMinMax(v, -(b.max - 1), b.max-1)
  2178  			return
  2179  		}
  2180  		if !(a.nonnegative() && b.nonnegative()) {
  2181  			// TODO: we could handle signed limits but I didn't bother.
  2182  			return
  2183  		}
  2184  		if a.min >= 0 && b.min > 0 {
  2185  			ft.setNonNegative(v)
  2186  		}
  2187  	}
  2188  	// Underflow in the arithmetic below is ok, it gives to MaxUint64 which does nothing to the limit.
  2189  	ft.unsignedMax(v, min(a.umax, b.umax-1))
  2190  }
  2191  
  2192  // getBranch returns the range restrictions added by p
  2193  // when reaching b. p is the immediate dominator of b.
  2194  func getBranch(sdom SparseTree, p *Block, b *Block) branch {
  2195  	if p == nil {
  2196  		return unknown
  2197  	}
  2198  	switch p.Kind {
  2199  	case BlockIf:
  2200  		// If p and p.Succs[0] are dominators it means that every path
  2201  		// from entry to b passes through p and p.Succs[0]. We care that
  2202  		// no path from entry to b passes through p.Succs[1]. If p.Succs[0]
  2203  		// has one predecessor then (apart from the degenerate case),
  2204  		// there is no path from entry that can reach b through p.Succs[1].
  2205  		// TODO: how about p->yes->b->yes, i.e. a loop in yes.
  2206  		if sdom.IsAncestorEq(p.Succs[0].b, b) && len(p.Succs[0].b.Preds) == 1 {
  2207  			return positive
  2208  		}
  2209  		if sdom.IsAncestorEq(p.Succs[1].b, b) && len(p.Succs[1].b.Preds) == 1 {
  2210  			return negative
  2211  		}
  2212  	case BlockJumpTable:
  2213  		// TODO: this loop can lead to quadratic behavior, as
  2214  		// getBranch can be called len(p.Succs) times.
  2215  		for i, e := range p.Succs {
  2216  			if sdom.IsAncestorEq(e.b, b) && len(e.b.Preds) == 1 {
  2217  				return jumpTable0 + branch(i)
  2218  			}
  2219  		}
  2220  	}
  2221  	return unknown
  2222  }
  2223  
  2224  // addIndVarRestrictions updates the factsTables ft with the facts
  2225  // learned from the induction variable indVar which drives the loop
  2226  // starting in Block b.
  2227  func addIndVarRestrictions(ft *factsTable, b *Block, iv indVar) {
  2228  	d := signed
  2229  	if ft.isNonNegative(iv.min) && ft.isNonNegative(iv.max) {
  2230  		d |= unsigned
  2231  	}
  2232  
  2233  	if iv.flags&indVarMinExc == 0 {
  2234  		addRestrictions(b, ft, d, iv.min, iv.ind, lt|eq)
  2235  	} else {
  2236  		addRestrictions(b, ft, d, iv.min, iv.ind, lt)
  2237  	}
  2238  
  2239  	if iv.flags&indVarMaxInc == 0 {
  2240  		addRestrictions(b, ft, d, iv.ind, iv.max, lt)
  2241  	} else {
  2242  		addRestrictions(b, ft, d, iv.ind, iv.max, lt|eq)
  2243  	}
  2244  }
  2245  
  2246  // addBranchRestrictions updates the factsTables ft with the facts learned when
  2247  // branching from Block b in direction br.
  2248  func addBranchRestrictions(ft *factsTable, b *Block, br branch) {
  2249  	c := b.Controls[0]
  2250  	switch {
  2251  	case br == negative:
  2252  		ft.booleanFalse(c)
  2253  	case br == positive:
  2254  		ft.booleanTrue(c)
  2255  	case br >= jumpTable0:
  2256  		idx := br - jumpTable0
  2257  		val := int64(idx)
  2258  		if v, off := isConstDelta(c); v != nil {
  2259  			// Establish the bound on the underlying value we're switching on,
  2260  			// not on the offset-ed value used as the jump table index.
  2261  			c = v
  2262  			val -= off
  2263  		}
  2264  		ft.newLimit(c, limit{min: val, max: val, umin: uint64(val), umax: uint64(val)})
  2265  	default:
  2266  		panic("unknown branch")
  2267  	}
  2268  }
  2269  
  2270  // addRestrictions updates restrictions from the immediate
  2271  // dominating block (p) using r.
  2272  func addRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r relation) {
  2273  	if t == 0 {
  2274  		// Trivial case: nothing to do.
  2275  		// Should not happen, but just in case.
  2276  		return
  2277  	}
  2278  	for i := domain(1); i <= t; i <<= 1 {
  2279  		if t&i == 0 {
  2280  			continue
  2281  		}
  2282  		ft.update(parent, v, w, i, r)
  2283  	}
  2284  }
  2285  
  2286  func unsignedAddOverflows(a, b uint64, t *types.Type) bool {
  2287  	switch t.Size() {
  2288  	case 8:
  2289  		return a+b < a
  2290  	case 4:
  2291  		return a+b > math.MaxUint32
  2292  	case 2:
  2293  		return a+b > math.MaxUint16
  2294  	case 1:
  2295  		return a+b > math.MaxUint8
  2296  	default:
  2297  		panic("unreachable")
  2298  	}
  2299  }
  2300  
  2301  func signedAddOverflowsOrUnderflows(a, b int64, t *types.Type) bool {
  2302  	r := a + b
  2303  	switch t.Size() {
  2304  	case 8:
  2305  		return (a >= 0 && b >= 0 && r < 0) || (a < 0 && b < 0 && r >= 0)
  2306  	case 4:
  2307  		return r < math.MinInt32 || math.MaxInt32 < r
  2308  	case 2:
  2309  		return r < math.MinInt16 || math.MaxInt16 < r
  2310  	case 1:
  2311  		return r < math.MinInt8 || math.MaxInt8 < r
  2312  	default:
  2313  		panic("unreachable")
  2314  	}
  2315  }
  2316  
  2317  func unsignedSubUnderflows(a, b uint64) bool {
  2318  	return a < b
  2319  }
  2320  
  2321  // checkForChunkedIndexBounds looks for index expressions of the form
  2322  // A[i+delta] where delta < K and i <= len(A)-K.  That is, this is a chunked
  2323  // iteration where the index is not directly compared to the length.
  2324  // if isReslice, then delta can be equal to K.
  2325  func checkForChunkedIndexBounds(ft *factsTable, b *Block, index, bound *Value, isReslice bool) bool {
  2326  	if bound.Op != OpSliceLen && bound.Op != OpStringLen && bound.Op != OpSliceCap {
  2327  		return false
  2328  	}
  2329  
  2330  	// this is a slice bounds check against len or capacity,
  2331  	// and refers back to a prior check against length, which
  2332  	// will also work for the cap since that is not smaller
  2333  	// than the length.
  2334  
  2335  	slice := bound.Args[0]
  2336  	lim := ft.limits[index.ID]
  2337  	if lim.min < 0 {
  2338  		return false
  2339  	}
  2340  	i, delta := isConstDelta(index)
  2341  	if i == nil {
  2342  		return false
  2343  	}
  2344  	if delta < 0 {
  2345  		return false
  2346  	}
  2347  	// special case for blocked iteration over a slice.
  2348  	// slicelen > i + delta && <==== if clauses above
  2349  	// && index >= 0           <==== if clause above
  2350  	// delta >= 0 &&           <==== if clause above
  2351  	// slicelen-K >/>= x       <==== checked below
  2352  	// && K >=/> delta         <==== checked below
  2353  	// then v > w
  2354  	// example: i <=/< len - 4/3 means i+{0,1,2,3} are legal indices
  2355  	for o := ft.orderings[i.ID]; o != nil; o = o.next {
  2356  		if o.d != signed {
  2357  			continue
  2358  		}
  2359  		if ow := o.w; ow.Op == OpAdd64 {
  2360  			var lenOffset *Value
  2361  			if bound := ow.Args[0]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2362  				lenOffset = ow.Args[1]
  2363  			} else if bound := ow.Args[1]; (bound.Op == OpSliceLen || bound.Op == OpStringLen) && bound.Args[0] == slice {
  2364  				lenOffset = ow.Args[0]
  2365  			}
  2366  			if lenOffset == nil || lenOffset.Op != OpConst64 {
  2367  				continue
  2368  			}
  2369  			if K := -lenOffset.AuxInt; K >= 0 {
  2370  				or := o.r
  2371  				if isReslice {
  2372  					K++
  2373  				}
  2374  				if or == lt {
  2375  					or = lt | eq
  2376  					K++
  2377  				}
  2378  				if K < 0 { // We hate thinking about overflow
  2379  					continue
  2380  				}
  2381  
  2382  				if delta < K && or == lt|eq {
  2383  					return true
  2384  				}
  2385  			}
  2386  		}
  2387  	}
  2388  	return false
  2389  }
  2390  
  2391  func addLocalFacts(ft *factsTable, b *Block) {
  2392  	ft.topoSortValuesInBlock(b)
  2393  
  2394  	for _, v := range b.Values {
  2395  		// Propagate constant ranges before relative relations to get
  2396  		// the most up-to-date constant bounds for isNonNegative calls.
  2397  		ft.flowLimit(v)
  2398  
  2399  		switch v.Op {
  2400  		case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2401  			x := ft.limits[v.Args[0].ID]
  2402  			y := ft.limits[v.Args[1].ID]
  2403  			if !unsignedAddOverflows(x.umax, y.umax, v.Type) {
  2404  				r := gt
  2405  				if x.maybeZero() {
  2406  					r |= eq
  2407  				}
  2408  				ft.update(b, v, v.Args[1], unsigned, r)
  2409  				r = gt
  2410  				if y.maybeZero() {
  2411  					r |= eq
  2412  				}
  2413  				ft.update(b, v, v.Args[0], unsigned, r)
  2414  			}
  2415  			if x.min >= 0 && !signedAddOverflowsOrUnderflows(x.max, y.max, v.Type) {
  2416  				r := gt
  2417  				if x.maybeZero() {
  2418  					r |= eq
  2419  				}
  2420  				ft.update(b, v, v.Args[1], signed, r)
  2421  			}
  2422  			if y.min >= 0 && !signedAddOverflowsOrUnderflows(x.max, y.max, v.Type) {
  2423  				r := gt
  2424  				if y.maybeZero() {
  2425  					r |= eq
  2426  				}
  2427  				ft.update(b, v, v.Args[0], signed, r)
  2428  			}
  2429  			if x.max <= 0 && !signedAddOverflowsOrUnderflows(x.min, y.min, v.Type) {
  2430  				r := lt
  2431  				if x.maybeZero() {
  2432  					r |= eq
  2433  				}
  2434  				ft.update(b, v, v.Args[1], signed, r)
  2435  			}
  2436  			if y.max <= 0 && !signedAddOverflowsOrUnderflows(x.min, y.min, v.Type) {
  2437  				r := lt
  2438  				if y.maybeZero() {
  2439  					r |= eq
  2440  				}
  2441  				ft.update(b, v, v.Args[0], signed, r)
  2442  			}
  2443  		case OpSub64, OpSub32, OpSub16, OpSub8:
  2444  			x := ft.limits[v.Args[0].ID]
  2445  			y := ft.limits[v.Args[1].ID]
  2446  			if !unsignedSubUnderflows(x.umin, y.umax) {
  2447  				r := lt
  2448  				if y.maybeZero() {
  2449  					r |= eq
  2450  				}
  2451  				ft.update(b, v, v.Args[0], unsigned, r)
  2452  			}
  2453  			// FIXME: we could also do signed facts but the overflow checks are much trickier and I don't need it yet.
  2454  		case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
  2455  			ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2456  			ft.update(b, v, v.Args[1], unsigned, lt|eq)
  2457  			if ft.isNonNegative(v.Args[0]) {
  2458  				ft.update(b, v, v.Args[0], signed, lt|eq)
  2459  			}
  2460  			if ft.isNonNegative(v.Args[1]) {
  2461  				ft.update(b, v, v.Args[1], signed, lt|eq)
  2462  			}
  2463  		case OpOr64, OpOr32, OpOr16, OpOr8:
  2464  			// TODO: investigate how to always add facts without much slowdown, see issue #57959
  2465  			//ft.update(b, v, v.Args[0], unsigned, gt|eq)
  2466  			//ft.update(b, v, v.Args[1], unsigned, gt|eq)
  2467  		case OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  2468  			if !ft.isNonNegative(v.Args[1]) {
  2469  				break
  2470  			}
  2471  			fallthrough
  2472  		case OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8,
  2473  			OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  2474  			OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  2475  			OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8:
  2476  			if !ft.isNonNegative(v.Args[0]) {
  2477  				break
  2478  			}
  2479  			fallthrough
  2480  		case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
  2481  			OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
  2482  			OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  2483  			OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  2484  			OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8:
  2485  			switch add := v.Args[0]; add.Op {
  2486  			// round-up division pattern; given:
  2487  			// v = (x + y) / z
  2488  			// if y < z then v <= x
  2489  			case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2490  				z := v.Args[1]
  2491  				zl := ft.limits[z.ID]
  2492  				var uminDivisor uint64
  2493  				switch v.Op {
  2494  				case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
  2495  					OpDiv64, OpDiv32, OpDiv16, OpDiv8:
  2496  					uminDivisor = zl.umin
  2497  				case OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
  2498  					OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
  2499  					OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
  2500  					OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8,
  2501  					OpRsh8x64, OpRsh8x32, OpRsh8x16, OpRsh8x8,
  2502  					OpRsh16x64, OpRsh16x32, OpRsh16x16, OpRsh16x8,
  2503  					OpRsh32x64, OpRsh32x32, OpRsh32x16, OpRsh32x8,
  2504  					OpRsh64x64, OpRsh64x32, OpRsh64x16, OpRsh64x8:
  2505  					uminDivisor = 1 << zl.umin
  2506  				default:
  2507  					panic("unreachable")
  2508  				}
  2509  
  2510  				x := add.Args[0]
  2511  				xl := ft.limits[x.ID]
  2512  				y := add.Args[1]
  2513  				yl := ft.limits[y.ID]
  2514  				if !unsignedAddOverflows(xl.umax, yl.umax, add.Type) {
  2515  					if xl.umax < uminDivisor {
  2516  						ft.update(b, v, y, unsigned, lt|eq)
  2517  					}
  2518  					if yl.umax < uminDivisor {
  2519  						ft.update(b, v, x, unsigned, lt|eq)
  2520  					}
  2521  				}
  2522  			}
  2523  			ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2524  		case OpMod64, OpMod32, OpMod16, OpMod8:
  2525  			if !ft.isNonNegative(v.Args[0]) || !ft.isNonNegative(v.Args[1]) {
  2526  				break
  2527  			}
  2528  			fallthrough
  2529  		case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
  2530  			ft.update(b, v, v.Args[0], unsigned, lt|eq)
  2531  			// Note: we have to be careful that this doesn't imply
  2532  			// that the modulus is >0, which isn't true until *after*
  2533  			// the mod instruction executes (and thus panics if the
  2534  			// modulus is 0). See issue 67625.
  2535  			ft.update(b, v, v.Args[1], unsigned, lt)
  2536  		case OpStringLen:
  2537  			if v.Args[0].Op == OpStringMake {
  2538  				ft.update(b, v, v.Args[0].Args[1], signed, eq)
  2539  			}
  2540  		case OpSliceLen:
  2541  			if v.Args[0].Op == OpSliceMake {
  2542  				ft.update(b, v, v.Args[0].Args[1], signed, eq)
  2543  			}
  2544  		case OpSliceCap:
  2545  			if v.Args[0].Op == OpSliceMake {
  2546  				ft.update(b, v, v.Args[0].Args[2], signed, eq)
  2547  			}
  2548  		case OpIsInBounds:
  2549  			if checkForChunkedIndexBounds(ft, b, v.Args[0], v.Args[1], false) {
  2550  				if b.Func.pass.debug > 0 {
  2551  					b.Func.Warnl(v.Pos, "Proved %s for blocked indexing", v.Op)
  2552  				}
  2553  				ft.booleanTrue(v)
  2554  			}
  2555  		case OpIsSliceInBounds:
  2556  			if checkForChunkedIndexBounds(ft, b, v.Args[0], v.Args[1], true) {
  2557  				if b.Func.pass.debug > 0 {
  2558  					b.Func.Warnl(v.Pos, "Proved %s for blocked reslicing", v.Op)
  2559  				}
  2560  				ft.booleanTrue(v)
  2561  			}
  2562  		case OpPhi:
  2563  			addLocalFactsPhi(ft, v)
  2564  		}
  2565  	}
  2566  }
  2567  
  2568  func addLocalFactsPhi(ft *factsTable, v *Value) {
  2569  	// Look for phis that implement min/max.
  2570  	//   z:
  2571  	//      c = Less64 x y (or other Less/Leq operation)
  2572  	//      If c -> bx by
  2573  	//   bx: <- z
  2574  	//       -> b ...
  2575  	//   by: <- z
  2576  	//      -> b ...
  2577  	//   b: <- bx by
  2578  	//      v = Phi x y
  2579  	// Then v is either min or max of x,y.
  2580  	// If it is the min, then we deduce v <= x && v <= y.
  2581  	// If it is the max, then we deduce v >= x && v >= y.
  2582  	// The min case is useful for the copy builtin, see issue 16833.
  2583  	if len(v.Args) != 2 {
  2584  		return
  2585  	}
  2586  	b := v.Block
  2587  	x := v.Args[0]
  2588  	y := v.Args[1]
  2589  	bx := b.Preds[0].b
  2590  	by := b.Preds[1].b
  2591  	var z *Block // branch point
  2592  	switch {
  2593  	case bx == by: // bx == by == z case
  2594  		z = bx
  2595  	case by.uniquePred() == bx: // bx == z case
  2596  		z = bx
  2597  	case bx.uniquePred() == by: // by == z case
  2598  		z = by
  2599  	case bx.uniquePred() == by.uniquePred():
  2600  		z = bx.uniquePred()
  2601  	}
  2602  	if z == nil || z.Kind != BlockIf {
  2603  		return
  2604  	}
  2605  	c := z.Controls[0]
  2606  	if len(c.Args) != 2 {
  2607  		return
  2608  	}
  2609  	var isMin bool // if c, a less-than comparison, is true, phi chooses x.
  2610  	if bx == z {
  2611  		isMin = b.Preds[0].i == 0
  2612  	} else {
  2613  		isMin = bx.Preds[0].i == 0
  2614  	}
  2615  	if c.Args[0] == x && c.Args[1] == y {
  2616  		// ok
  2617  	} else if c.Args[0] == y && c.Args[1] == x {
  2618  		// Comparison is reversed from how the values are listed in the Phi.
  2619  		isMin = !isMin
  2620  	} else {
  2621  		// Not comparing x and y.
  2622  		return
  2623  	}
  2624  	var dom domain
  2625  	switch c.Op {
  2626  	case OpLess64, OpLess32, OpLess16, OpLess8, OpLeq64, OpLeq32, OpLeq16, OpLeq8:
  2627  		dom = signed
  2628  	case OpLess64U, OpLess32U, OpLess16U, OpLess8U, OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U:
  2629  		dom = unsigned
  2630  	default:
  2631  		return
  2632  	}
  2633  	var rel relation
  2634  	if isMin {
  2635  		rel = lt | eq
  2636  	} else {
  2637  		rel = gt | eq
  2638  	}
  2639  	ft.update(b, v, x, dom, rel)
  2640  	ft.update(b, v, y, dom, rel)
  2641  }
  2642  
  2643  var ctzNonZeroOp = map[Op]Op{
  2644  	OpCtz8:  OpCtz8NonZero,
  2645  	OpCtz16: OpCtz16NonZero,
  2646  	OpCtz32: OpCtz32NonZero,
  2647  	OpCtz64: OpCtz64NonZero,
  2648  }
  2649  var mostNegativeDividend = map[Op]int64{
  2650  	OpDiv16: -1 << 15,
  2651  	OpMod16: -1 << 15,
  2652  	OpDiv32: -1 << 31,
  2653  	OpMod32: -1 << 31,
  2654  	OpDiv64: -1 << 63,
  2655  	OpMod64: -1 << 63,
  2656  }
  2657  var unsignedOp = map[Op]Op{
  2658  	OpDiv8:     OpDiv8u,
  2659  	OpDiv16:    OpDiv16u,
  2660  	OpDiv32:    OpDiv32u,
  2661  	OpDiv64:    OpDiv64u,
  2662  	OpMod8:     OpMod8u,
  2663  	OpMod16:    OpMod16u,
  2664  	OpMod32:    OpMod32u,
  2665  	OpMod64:    OpMod64u,
  2666  	OpRsh8x8:   OpRsh8Ux8,
  2667  	OpRsh8x16:  OpRsh8Ux16,
  2668  	OpRsh8x32:  OpRsh8Ux32,
  2669  	OpRsh8x64:  OpRsh8Ux64,
  2670  	OpRsh16x8:  OpRsh16Ux8,
  2671  	OpRsh16x16: OpRsh16Ux16,
  2672  	OpRsh16x32: OpRsh16Ux32,
  2673  	OpRsh16x64: OpRsh16Ux64,
  2674  	OpRsh32x8:  OpRsh32Ux8,
  2675  	OpRsh32x16: OpRsh32Ux16,
  2676  	OpRsh32x32: OpRsh32Ux32,
  2677  	OpRsh32x64: OpRsh32Ux64,
  2678  	OpRsh64x8:  OpRsh64Ux8,
  2679  	OpRsh64x16: OpRsh64Ux16,
  2680  	OpRsh64x32: OpRsh64Ux32,
  2681  	OpRsh64x64: OpRsh64Ux64,
  2682  }
  2683  
  2684  var bytesizeToConst = [...]Op{
  2685  	8 / 8:  OpConst8,
  2686  	16 / 8: OpConst16,
  2687  	32 / 8: OpConst32,
  2688  	64 / 8: OpConst64,
  2689  }
  2690  var bytesizeToNeq = [...]Op{
  2691  	8 / 8:  OpNeq8,
  2692  	16 / 8: OpNeq16,
  2693  	32 / 8: OpNeq32,
  2694  	64 / 8: OpNeq64,
  2695  }
  2696  var bytesizeToAnd = [...]Op{
  2697  	8 / 8:  OpAnd8,
  2698  	16 / 8: OpAnd16,
  2699  	32 / 8: OpAnd32,
  2700  	64 / 8: OpAnd64,
  2701  }
  2702  
  2703  var invertEqNeqOp = map[Op]Op{
  2704  	OpEq8:  OpNeq8,
  2705  	OpNeq8: OpEq8,
  2706  
  2707  	OpEq16:  OpNeq16,
  2708  	OpNeq16: OpEq16,
  2709  
  2710  	OpEq32:  OpNeq32,
  2711  	OpNeq32: OpEq32,
  2712  
  2713  	OpEq64:  OpNeq64,
  2714  	OpNeq64: OpEq64,
  2715  }
  2716  
  2717  // simplifyBlock simplifies some constant values in b and evaluates
  2718  // branches to non-uniquely dominated successors of b.
  2719  func simplifyBlock(sdom SparseTree, ft *factsTable, b *Block) {
  2720  	for iv, v := range b.Values {
  2721  		switch v.Op {
  2722  		case OpStaticLECall:
  2723  			if b.Func.pass.debug > 0 && len(v.Args) == 2 {
  2724  				fn := auxToCall(v.Aux).Fn
  2725  				if fn != nil && strings.Contains(fn.String(), "prove") {
  2726  					// Print bounds of any argument to single-arg function with "prove" in name,
  2727  					// for debugging and especially for test/prove.go.
  2728  					// (v.Args[1] is mem).
  2729  					x := v.Args[0]
  2730  					b.Func.Warnl(v.Pos, "Proved %v (%v)", ft.limits[x.ID], x)
  2731  				}
  2732  			}
  2733  		case OpSlicemask:
  2734  			// Replace OpSlicemask operations in b with constants where possible.
  2735  			cap := v.Args[0]
  2736  			x, delta := isConstDelta(cap)
  2737  			if x != nil {
  2738  				// slicemask(x + y)
  2739  				// if x is larger than -y (y is negative), then slicemask is -1.
  2740  				lim := ft.limits[x.ID]
  2741  				if lim.umin > uint64(-delta) {
  2742  					if cap.Op == OpAdd64 {
  2743  						v.reset(OpConst64)
  2744  					} else {
  2745  						v.reset(OpConst32)
  2746  					}
  2747  					if b.Func.pass.debug > 0 {
  2748  						b.Func.Warnl(v.Pos, "Proved slicemask not needed")
  2749  					}
  2750  					v.AuxInt = -1
  2751  				}
  2752  				break
  2753  			}
  2754  			lim := ft.limits[cap.ID]
  2755  			if lim.umin > 0 {
  2756  				if cap.Type.Size() == 8 {
  2757  					v.reset(OpConst64)
  2758  				} else {
  2759  					v.reset(OpConst32)
  2760  				}
  2761  				if b.Func.pass.debug > 0 {
  2762  					b.Func.Warnl(v.Pos, "Proved slicemask not needed (by limit)")
  2763  				}
  2764  				v.AuxInt = -1
  2765  			}
  2766  
  2767  		case OpCtz8, OpCtz16, OpCtz32, OpCtz64:
  2768  			// On some architectures, notably amd64, we can generate much better
  2769  			// code for CtzNN if we know that the argument is non-zero.
  2770  			// Capture that information here for use in arch-specific optimizations.
  2771  			x := v.Args[0]
  2772  			lim := ft.limits[x.ID]
  2773  			if lim.umin > 0 || lim.min > 0 || lim.max < 0 {
  2774  				if b.Func.pass.debug > 0 {
  2775  					b.Func.Warnl(v.Pos, "Proved %v non-zero", v.Op)
  2776  				}
  2777  				v.Op = ctzNonZeroOp[v.Op]
  2778  			}
  2779  		case OpRsh8x8, OpRsh8x16, OpRsh8x32, OpRsh8x64,
  2780  			OpRsh16x8, OpRsh16x16, OpRsh16x32, OpRsh16x64,
  2781  			OpRsh32x8, OpRsh32x16, OpRsh32x32, OpRsh32x64,
  2782  			OpRsh64x8, OpRsh64x16, OpRsh64x32, OpRsh64x64:
  2783  			if ft.isNonNegative(v.Args[0]) {
  2784  				if b.Func.pass.debug > 0 {
  2785  					b.Func.Warnl(v.Pos, "Proved %v is unsigned", v.Op)
  2786  				}
  2787  				v.Op = unsignedOp[v.Op]
  2788  			}
  2789  			fallthrough
  2790  		case OpLsh8x8, OpLsh8x16, OpLsh8x32, OpLsh8x64,
  2791  			OpLsh16x8, OpLsh16x16, OpLsh16x32, OpLsh16x64,
  2792  			OpLsh32x8, OpLsh32x16, OpLsh32x32, OpLsh32x64,
  2793  			OpLsh64x8, OpLsh64x16, OpLsh64x32, OpLsh64x64,
  2794  			OpRsh8Ux8, OpRsh8Ux16, OpRsh8Ux32, OpRsh8Ux64,
  2795  			OpRsh16Ux8, OpRsh16Ux16, OpRsh16Ux32, OpRsh16Ux64,
  2796  			OpRsh32Ux8, OpRsh32Ux16, OpRsh32Ux32, OpRsh32Ux64,
  2797  			OpRsh64Ux8, OpRsh64Ux16, OpRsh64Ux32, OpRsh64Ux64:
  2798  			// Check whether, for a << b, we know that b
  2799  			// is strictly less than the number of bits in a.
  2800  			by := v.Args[1]
  2801  			lim := ft.limits[by.ID]
  2802  			bits := 8 * v.Args[0].Type.Size()
  2803  			if lim.umax < uint64(bits) || (lim.max < bits && ft.isNonNegative(by)) {
  2804  				v.AuxInt = 1 // see shiftIsBounded
  2805  				if b.Func.pass.debug > 0 && !by.isGenericIntConst() {
  2806  					b.Func.Warnl(v.Pos, "Proved %v bounded", v.Op)
  2807  				}
  2808  			}
  2809  		case OpDiv8, OpDiv16, OpDiv32, OpDiv64, OpMod8, OpMod16, OpMod32, OpMod64:
  2810  			p, q := ft.limits[v.Args[0].ID], ft.limits[v.Args[1].ID] // p/q
  2811  			if p.nonnegative() && q.nonnegative() {
  2812  				if b.Func.pass.debug > 0 {
  2813  					b.Func.Warnl(v.Pos, "Proved %v is unsigned", v.Op)
  2814  				}
  2815  				v.Op = unsignedOp[v.Op]
  2816  				v.AuxInt = 0
  2817  				break
  2818  			}
  2819  			// Fixup code can be avoided on x86 if we know
  2820  			//  the divisor is not -1 or the dividend > MinIntNN.
  2821  			if v.Op != OpDiv8 && v.Op != OpMod8 && (q.max < -1 || q.min > -1 || p.min > mostNegativeDividend[v.Op]) {
  2822  				// See DivisionNeedsFixUp in rewrite.go.
  2823  				// v.AuxInt = 1 means we have proved that the divisor is not -1
  2824  				// or that the dividend is not the most negative integer,
  2825  				// so we do not need to add fix-up code.
  2826  				if b.Func.pass.debug > 0 {
  2827  					b.Func.Warnl(v.Pos, "Proved %v does not need fix-up", v.Op)
  2828  				}
  2829  				// Only usable on amd64 and 386, and only for ≥ 16-bit ops.
  2830  				// Don't modify AuxInt on other architectures, as that can interfere with CSE.
  2831  				// (Print the debug info above always, so that test/prove.go can be
  2832  				// checked on non-x86 systems.)
  2833  				// TODO: add other architectures?
  2834  				if b.Func.Config.arch == "386" || b.Func.Config.arch == "amd64" {
  2835  					v.AuxInt = 1
  2836  				}
  2837  			}
  2838  		case OpMul64, OpMul32, OpMul16, OpMul8:
  2839  			if vl := ft.limits[v.ID]; vl.min == vl.max || vl.umin == vl.umax {
  2840  				// v is going to be constant folded away; don't "optimize" it.
  2841  				break
  2842  			}
  2843  			x := v.Args[0]
  2844  			xl := ft.limits[x.ID]
  2845  			y := v.Args[1]
  2846  			yl := ft.limits[y.ID]
  2847  			if xl.umin == xl.umax && isPowerOfTwo(xl.umin) ||
  2848  				xl.min == xl.max && isPowerOfTwo(xl.min) ||
  2849  				yl.umin == yl.umax && isPowerOfTwo(yl.umin) ||
  2850  				yl.min == yl.max && isPowerOfTwo(yl.min) {
  2851  				// 0,1 * a power of two is better done as a shift
  2852  				break
  2853  			}
  2854  			switch xOne, yOne := xl.umax <= 1, yl.umax <= 1; {
  2855  			case xOne && yOne:
  2856  				v.Op = bytesizeToAnd[v.Type.Size()]
  2857  				if b.Func.pass.debug > 0 {
  2858  					b.Func.Warnl(v.Pos, "Rewrote Mul %v into And", v)
  2859  				}
  2860  			case yOne && b.Func.Config.haveCondSelect:
  2861  				x, y = y, x
  2862  				fallthrough
  2863  			case xOne && b.Func.Config.haveCondSelect:
  2864  				if !canCondSelect(v, b.Func.Config.arch, nil) {
  2865  					break
  2866  				}
  2867  				zero := b.Func.constVal(bytesizeToConst[v.Type.Size()], v.Type, 0, true)
  2868  				ft.initLimitForNewValue(zero)
  2869  				check := b.NewValue2(v.Pos, bytesizeToNeq[v.Type.Size()], types.Types[types.TBOOL], zero, x)
  2870  				ft.initLimitForNewValue(check)
  2871  				v.reset(OpCondSelect)
  2872  				v.AddArg3(y, zero, check)
  2873  
  2874  				// FIXME: workaround for go.dev/issues/76060
  2875  				// we need to schedule the Neq before the CondSelect even tho
  2876  				// scheduling is meaningless until we reach the schedule pass.
  2877  				if b.Values[len(b.Values)-1] != check {
  2878  					panic("unreachable; failed sanity check, new value isn't at the end of the block")
  2879  				}
  2880  				b.Values[iv], b.Values[len(b.Values)-1] = b.Values[len(b.Values)-1], b.Values[iv]
  2881  
  2882  				if b.Func.pass.debug > 0 {
  2883  					b.Func.Warnl(v.Pos, "Rewrote Mul %v into CondSelect; %v is bool", v, x)
  2884  				}
  2885  			}
  2886  		case OpEq64, OpEq32, OpEq16, OpEq8,
  2887  			OpNeq64, OpNeq32, OpNeq16, OpNeq8:
  2888  			// Canonicalize:
  2889  			// [0,1] != 1 → [0,1] == 0
  2890  			// [0,1] == 1 → [0,1] != 0
  2891  			// Comparison with zero often encode smaller.
  2892  			xPos, yPos := 0, 1
  2893  			x, y := v.Args[xPos], v.Args[yPos]
  2894  			xl, yl := ft.limits[x.ID], ft.limits[y.ID]
  2895  			xConst, xIsConst := xl.constValue()
  2896  			yConst, yIsConst := yl.constValue()
  2897  			switch {
  2898  			case xIsConst && yIsConst:
  2899  			case xIsConst:
  2900  				xPos, yPos = yPos, xPos
  2901  				x, y = y, x
  2902  				xl, yl = yl, xl
  2903  				xConst, yConst = yConst, xConst
  2904  				fallthrough
  2905  			case yIsConst:
  2906  				if yConst != 1 ||
  2907  					xl.umax > 1 {
  2908  					break
  2909  				}
  2910  				zero := b.Func.constVal(bytesizeToConst[x.Type.Size()], x.Type, 0, true)
  2911  				ft.initLimitForNewValue(zero)
  2912  				oldOp := v.Op
  2913  				v.Op = invertEqNeqOp[v.Op]
  2914  				v.SetArg(yPos, zero)
  2915  				if b.Func.pass.debug > 0 {
  2916  					b.Func.Warnl(v.Pos, "Rewrote %v (%v) %v argument is boolean-like; rewrote to %v against 0", v, oldOp, x, v.Op)
  2917  				}
  2918  			}
  2919  		}
  2920  
  2921  		// Fold provable constant results.
  2922  		// Helps in cases where we reuse a value after branching on its equality.
  2923  		for i, arg := range v.Args {
  2924  			lim := ft.limits[arg.ID]
  2925  			constValue, ok := lim.constValue()
  2926  			if !ok {
  2927  				continue
  2928  			}
  2929  			switch arg.Op {
  2930  			case OpConst64, OpConst32, OpConst16, OpConst8, OpConstBool, OpConstNil:
  2931  				continue
  2932  			}
  2933  			typ := arg.Type
  2934  			f := b.Func
  2935  			var c *Value
  2936  			switch {
  2937  			case typ.IsBoolean():
  2938  				c = f.ConstBool(typ, constValue != 0)
  2939  			case typ.IsInteger() && typ.Size() == 1:
  2940  				c = f.ConstInt8(typ, int8(constValue))
  2941  			case typ.IsInteger() && typ.Size() == 2:
  2942  				c = f.ConstInt16(typ, int16(constValue))
  2943  			case typ.IsInteger() && typ.Size() == 4:
  2944  				c = f.ConstInt32(typ, int32(constValue))
  2945  			case typ.IsInteger() && typ.Size() == 8:
  2946  				c = f.ConstInt64(typ, constValue)
  2947  			case typ.IsPtrShaped():
  2948  				if constValue == 0 {
  2949  					c = f.ConstNil(typ)
  2950  				} else {
  2951  					// Not sure how this might happen, but if it
  2952  					// does, just skip it.
  2953  					continue
  2954  				}
  2955  			default:
  2956  				// Not sure how this might happen, but if it
  2957  				// does, just skip it.
  2958  				continue
  2959  			}
  2960  			v.SetArg(i, c)
  2961  			ft.initLimitForNewValue(c)
  2962  			if b.Func.pass.debug > 1 {
  2963  				b.Func.Warnl(v.Pos, "Proved %v's arg %d (%v) is constant %d", v, i, arg, constValue)
  2964  			}
  2965  		}
  2966  	}
  2967  
  2968  	if b.Kind != BlockIf {
  2969  		return
  2970  	}
  2971  
  2972  	// Consider outgoing edges from this block.
  2973  	parent := b
  2974  	for i, branch := range [...]branch{positive, negative} {
  2975  		child := parent.Succs[i].b
  2976  		if getBranch(sdom, parent, child) != unknown {
  2977  			// For edges to uniquely dominated blocks, we
  2978  			// already did this when we visited the child.
  2979  			continue
  2980  		}
  2981  		// For edges to other blocks, this can trim a branch
  2982  		// even if we couldn't get rid of the child itself.
  2983  		ft.checkpoint()
  2984  		addBranchRestrictions(ft, parent, branch)
  2985  		unsat := ft.unsat
  2986  		ft.restore()
  2987  		if unsat {
  2988  			// This branch is impossible, so remove it
  2989  			// from the block.
  2990  			removeBranch(parent, branch)
  2991  			// No point in considering the other branch.
  2992  			// (It *is* possible for both to be
  2993  			// unsatisfiable since the fact table is
  2994  			// incomplete. We could turn this into a
  2995  			// BlockExit, but it doesn't seem worth it.)
  2996  			break
  2997  		}
  2998  	}
  2999  }
  3000  
  3001  func removeBranch(b *Block, branch branch) {
  3002  	c := b.Controls[0]
  3003  	if c != nil && b.Func.pass.debug > 0 {
  3004  		verb := "Proved"
  3005  		if branch == positive {
  3006  			verb = "Disproved"
  3007  		}
  3008  		if b.Func.pass.debug > 1 {
  3009  			b.Func.Warnl(b.Pos, "%s %s (%s)", verb, c.Op, c)
  3010  		} else {
  3011  			b.Func.Warnl(b.Pos, "%s %s", verb, c.Op)
  3012  		}
  3013  	}
  3014  	if c != nil && c.Pos.IsStmt() == src.PosIsStmt && c.Pos.SameFileAndLine(b.Pos) {
  3015  		// attempt to preserve statement marker.
  3016  		b.Pos = b.Pos.WithIsStmt()
  3017  	}
  3018  	if branch == positive || branch == negative {
  3019  		b.Kind = BlockFirst
  3020  		b.ResetControls()
  3021  		if branch == positive {
  3022  			b.swapSuccessors()
  3023  		}
  3024  	} else {
  3025  		// TODO: figure out how to remove an entry from a jump table
  3026  	}
  3027  }
  3028  
  3029  // isConstDelta returns non-nil if v is equivalent to w+delta (signed).
  3030  func isConstDelta(v *Value) (w *Value, delta int64) {
  3031  	cop := OpConst64
  3032  	switch v.Op {
  3033  	case OpAdd32, OpSub32:
  3034  		cop = OpConst32
  3035  	case OpAdd16, OpSub16:
  3036  		cop = OpConst16
  3037  	case OpAdd8, OpSub8:
  3038  		cop = OpConst8
  3039  	}
  3040  	switch v.Op {
  3041  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  3042  		if v.Args[0].Op == cop {
  3043  			return v.Args[1], v.Args[0].AuxInt
  3044  		}
  3045  		if v.Args[1].Op == cop {
  3046  			return v.Args[0], v.Args[1].AuxInt
  3047  		}
  3048  	case OpSub64, OpSub32, OpSub16, OpSub8:
  3049  		if v.Args[1].Op == cop {
  3050  			aux := v.Args[1].AuxInt
  3051  			if aux != -aux { // Overflow; too bad
  3052  				return v.Args[0], -aux
  3053  			}
  3054  		}
  3055  	}
  3056  	return nil, 0
  3057  }
  3058  
  3059  // isCleanExt reports whether v is the result of a value-preserving
  3060  // sign or zero extension.
  3061  func isCleanExt(v *Value) bool {
  3062  	switch v.Op {
  3063  	case OpSignExt8to16, OpSignExt8to32, OpSignExt8to64,
  3064  		OpSignExt16to32, OpSignExt16to64, OpSignExt32to64:
  3065  		// signed -> signed is the only value-preserving sign extension
  3066  		return v.Args[0].Type.IsSigned() && v.Type.IsSigned()
  3067  
  3068  	case OpZeroExt8to16, OpZeroExt8to32, OpZeroExt8to64,
  3069  		OpZeroExt16to32, OpZeroExt16to64, OpZeroExt32to64:
  3070  		// unsigned -> signed/unsigned are value-preserving zero extensions
  3071  		return !v.Args[0].Type.IsSigned()
  3072  	}
  3073  	return false
  3074  }
  3075  
  3076  func getDependencyScore(scores []uint, v *Value) (score uint) {
  3077  	if score = scores[v.ID]; score != 0 {
  3078  		return score
  3079  	}
  3080  	defer func() {
  3081  		scores[v.ID] = score
  3082  	}()
  3083  	if v.Op == OpPhi {
  3084  		return 1
  3085  	}
  3086  	score = 2 // NIT(@Jorropo): always order phis first to make GOSSAFUNC pretty.
  3087  	for _, a := range v.Args {
  3088  		if a.Block != v.Block {
  3089  			continue
  3090  		}
  3091  		score = max(score, getDependencyScore(scores, a)+1)
  3092  	}
  3093  	return score
  3094  }
  3095  
  3096  // topoSortValuesInBlock ensure ranging over b.Values visit values before they are being used.
  3097  // It does not consider dependencies with other blocks; thus Phi nodes are considered to not have any dependecies.
  3098  // The result is always determistic and does not depend on the previous slice ordering.
  3099  func (ft *factsTable) topoSortValuesInBlock(b *Block) {
  3100  	f := b.Func
  3101  	want := f.NumValues()
  3102  
  3103  	scores := ft.reusedTopoSortScoresTable
  3104  	if want <= cap(scores) {
  3105  		scores = scores[:want]
  3106  	} else {
  3107  		if cap(scores) > 0 {
  3108  			f.Cache.freeUintSlice(scores)
  3109  		}
  3110  		scores = f.Cache.allocUintSlice(want)
  3111  		ft.reusedTopoSortScoresTable = scores
  3112  	}
  3113  
  3114  	for _, v := range b.Values {
  3115  		scores[v.ID] = 0 // sentinel
  3116  	}
  3117  
  3118  	slices.SortFunc(b.Values, func(a, b *Value) int {
  3119  		dependencyScoreA := getDependencyScore(scores, a)
  3120  		dependencyScoreB := getDependencyScore(scores, b)
  3121  		if dependencyScoreA != dependencyScoreB {
  3122  			return cmp.Compare(dependencyScoreA, dependencyScoreB)
  3123  		}
  3124  		return cmp.Compare(a.ID, b.ID)
  3125  	})
  3126  }
  3127  

View as plain text