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

View as plain text