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

View as plain text