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

View as plain text