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  	"fmt"
     9  	"math"
    10  	"math/bits"
    11  
    12  	"cmd/compile/internal/ssa/ssaop"
    13  )
    14  
    15  // FitsInBitsU reports whether x fits in b bits (unsigned).
    16  func FitsInBitsU(x uint64, b uint) bool {
    17  	return x>>b == 0
    18  }
    19  
    20  // InitLimit sets initial constant limit for v.  This limit is based
    21  // only on the operation itself, not any of its input arguments. This
    22  // method is only used in two places, once when the prove pass startup
    23  // and the other when a new ssa value is created, both for init. (unlike
    24  // flowLimit, below, which computes additional constraints based on
    25  // ranges of opcode arguments).
    26  func InitLimit(v *Value) Limit {
    27  	if v.Type.IsBoolean() {
    28  		switch v.Op {
    29  		case ssaop.OpConstBool:
    30  			b := v.AuxInt
    31  			return Limit{Min: b, Max: b, Umin: uint64(b), Umax: uint64(b)}
    32  		default:
    33  			return Limit{Min: 0, Max: 1, Umin: 0, Umax: 1}
    34  		}
    35  	}
    36  	if v.Type.IsPtrShaped() { // These are the types that EqPtr/NeqPtr operate on, except uintptr.
    37  		switch v.Op {
    38  		case ssaop.OpConstNil:
    39  			return Limit{Min: 0, Max: 0, Umin: 0, Umax: 0}
    40  		case ssaop.OpAddr, ssaop.OpLocalAddr: // TODO: others?
    41  			l := NoLimit()
    42  			l.Umin = 1
    43  			return l
    44  		default:
    45  			return NoLimit()
    46  		}
    47  	}
    48  	if !v.Type.IsInteger() {
    49  		return NoLimit()
    50  	}
    51  
    52  	// Default limits based on type.
    53  	lim := NoLimitForBitsize(uint(v.Type.Size()) * 8)
    54  
    55  	// Tighter limits on some opcodes.
    56  	switch v.Op {
    57  	// constants
    58  	case ssaop.OpConst64:
    59  		lim = Limit{Min: v.AuxInt, Max: v.AuxInt, Umin: uint64(v.AuxInt), Umax: uint64(v.AuxInt)}
    60  	case ssaop.OpConst32:
    61  		lim = Limit{Min: v.AuxInt, Max: v.AuxInt, Umin: uint64(uint32(v.AuxInt)), Umax: uint64(uint32(v.AuxInt))}
    62  	case ssaop.OpConst16:
    63  		lim = Limit{Min: v.AuxInt, Max: v.AuxInt, Umin: uint64(uint16(v.AuxInt)), Umax: uint64(uint16(v.AuxInt))}
    64  	case ssaop.OpConst8:
    65  		lim = Limit{Min: v.AuxInt, Max: v.AuxInt, Umin: uint64(uint8(v.AuxInt)), Umax: uint64(uint8(v.AuxInt))}
    66  
    67  	// extensions
    68  	case ssaop.OpZeroExt8to64, ssaop.OpZeroExt8to32, ssaop.OpZeroExt8to16:
    69  		lim = lim.SignedMinMax(0, 1<<8-1)
    70  		lim = lim.UnsignedMax(1<<8 - 1)
    71  	case ssaop.OpZeroExt16to64, ssaop.OpZeroExt16to32:
    72  		lim = lim.SignedMinMax(0, 1<<16-1)
    73  		lim = lim.UnsignedMax(1<<16 - 1)
    74  	case ssaop.OpZeroExt32to64:
    75  		lim = lim.SignedMinMax(0, 1<<32-1)
    76  		lim = lim.UnsignedMax(1<<32 - 1)
    77  	case ssaop.OpSignExt8to64, ssaop.OpSignExt8to32, ssaop.OpSignExt8to16:
    78  		lim = lim.SignedMinMax(math.MinInt8, math.MaxInt8)
    79  	case ssaop.OpSignExt16to64, ssaop.OpSignExt16to32:
    80  		lim = lim.SignedMinMax(math.MinInt16, math.MaxInt16)
    81  	case ssaop.OpSignExt32to64:
    82  		lim = lim.SignedMinMax(math.MinInt32, math.MaxInt32)
    83  
    84  	// math/bits intrinsics
    85  	case ssaop.OpCtz64, ssaop.OpBitLen64, ssaop.OpPopCount64,
    86  		ssaop.OpCtz32, ssaop.OpBitLen32, ssaop.OpPopCount32,
    87  		ssaop.OpCtz16, ssaop.OpBitLen16, ssaop.OpPopCount16,
    88  		ssaop.OpCtz8, ssaop.OpBitLen8, ssaop.OpPopCount8:
    89  		lim = lim.UnsignedMax(uint64(v.Args[0].Type.Size() * 8))
    90  
    91  	// bool to uint8 conversion
    92  	case ssaop.OpCvtBoolToUint8:
    93  		lim = lim.UnsignedMax(1)
    94  
    95  	// length operations
    96  	case ssaop.OpSliceLen, ssaop.OpSliceCap:
    97  		f := v.Block.Func
    98  		elemSize := uint64(v.Args[0].Type.Elem().Size())
    99  		if elemSize > 0 {
   100  			heapSize := uint64(1)<<(uint64(f.Config.PtrSize)*8) - 1
   101  			maximumElementsFittingInHeap := heapSize / elemSize
   102  			lim = lim.UnsignedMax(maximumElementsFittingInHeap)
   103  		}
   104  		fallthrough
   105  	case ssaop.OpStringLen:
   106  		lim = lim.signedMin(0)
   107  	}
   108  
   109  	lim = lim.PropagateUnsignedSignedRelationship(uint(v.Type.Size()) * 8)
   110  
   111  	return lim
   112  }
   113  
   114  // a Limit records known upper and lower bounds for a value.
   115  //
   116  // If we have min>max or umin>umax, then this Limit is
   117  // called "unsatisfiable". When we encounter such a Limit, we
   118  // know that any code for which that Limit applies is unreachable.
   119  // We don't particularly care how unsatisfiable limits propagate,
   120  // including becoming satisfiable, because any optimization
   121  // decisions based on those limits only apply to unreachable code.
   122  type Limit struct {
   123  	Min, Max   int64  // min <= value <= max, signed
   124  	Umin, Umax uint64 // umin <= value <= umax, unsigned
   125  	// For booleans, we use 0==false, 1==true for both ranges
   126  	// For pointers, we use 0,0,0,0 for nil and minInt64,maxInt64,1,maxUint64 for nonnil
   127  }
   128  
   129  func NoLimit() Limit {
   130  	return NoLimitForBitsize(64)
   131  }
   132  
   133  // If x and y can add without overflow or underflow
   134  // (using b bits), SafeAdd returns x+y, true.
   135  // Otherwise, returns 0, false.
   136  func SafeAdd(x, y int64, b uint) (int64, bool) {
   137  	s := x + y
   138  	if x >= 0 && y >= 0 && s < 0 {
   139  		return 0, false // 64-bit overflow
   140  	}
   141  	if x < 0 && y < 0 && s >= 0 {
   142  		return 0, false // 64-bit underflow
   143  	}
   144  	if !fitsInBits(s, b) {
   145  		return 0, false
   146  	}
   147  	return s, true
   148  }
   149  
   150  // same as safeAdd but for subtraction.
   151  func SafeSub(x, y int64, b uint) (int64, bool) {
   152  	if y == math.MinInt64 {
   153  		if x == math.MaxInt64 {
   154  			return 0, false // 64-bit overflow
   155  		}
   156  		x++
   157  		y++
   158  	}
   159  	return SafeAdd(x, -y, b)
   160  }
   161  
   162  // same as safeAddU but for subtraction.
   163  func SafeSubU(x, y uint64, b uint) (uint64, bool) {
   164  	if x < y {
   165  		return 0, false // 64-bit underflow
   166  	}
   167  	s := x - y
   168  	if !FitsInBitsU(s, b) {
   169  		return 0, false
   170  	}
   171  	return s, true
   172  }
   173  
   174  func ConvertIntWithBitsize[Target uint64 | int64, Source uint64 | int64](x Source, bitsize uint) Target {
   175  	if Target(0)-1 < 0 {
   176  		// Signed target: sign-extend the low bitsize bits.
   177  		switch bitsize {
   178  		case 64:
   179  			return Target(int64(x))
   180  		case 32:
   181  			return Target(int32(x))
   182  		case 16:
   183  			return Target(int16(x))
   184  		case 8:
   185  			return Target(int8(x))
   186  		}
   187  	} else {
   188  		// Unsigned target: zero-extend the low bitsize bits.
   189  		switch bitsize {
   190  		case 64:
   191  			return Target(uint64(x))
   192  		case 32:
   193  			return Target(uint32(x))
   194  		case 16:
   195  			return Target(uint16(x))
   196  		case 8:
   197  			return Target(uint8(x))
   198  		}
   199  	}
   200  	panic("unreachable")
   201  }
   202  
   203  // fitsInBits reports whether x fits in b bits (signed).
   204  func fitsInBits(x int64, b uint) bool {
   205  	if b == 64 {
   206  		return true
   207  	}
   208  	m := int64(-1) << (b - 1)
   209  	M := -m - 1
   210  	return x >= m && x <= M
   211  }
   212  
   213  func NoLimitForBitsize(bitsize uint) Limit {
   214  	return Limit{Min: -(1 << (bitsize - 1)), Max: 1<<(bitsize-1) - 1, Umin: 0, Umax: 1<<bitsize - 1}
   215  }
   216  
   217  // same as safeAdd for unsigned arithmetic.
   218  func safeAddU(x, y uint64, b uint) (uint64, bool) {
   219  	s := x + y
   220  	if s < x || s < y {
   221  		return 0, false // 64-bit overflow
   222  	}
   223  	if !FitsInBitsU(s, b) {
   224  		return 0, false
   225  	}
   226  	return s, true
   227  }
   228  
   229  func (l Limit) PropagateUnsignedSignedRelationship(bitsize uint) Limit {
   230  	if l.Unsat() {
   231  		return l
   232  	}
   233  	if signWithBitsize(l.Min, bitsize) == signWithBitsize(l.Max, bitsize) {
   234  		l = l.UnsignedMinMax(ConvertIntWithBitsize[uint64](l.Min, bitsize), ConvertIntWithBitsize[uint64](l.Max, bitsize))
   235  	}
   236  
   237  	sumin, sumax := ConvertIntWithBitsize[int64](l.Umin, bitsize), ConvertIntWithBitsize[int64](l.Umax, bitsize)
   238  	if signWithBitsize(sumin, bitsize) == signWithBitsize(sumax, bitsize) {
   239  		l = l.SignedMinMax(sumin, sumax)
   240  	}
   241  
   242  	return l
   243  }
   244  
   245  // signWithBitsize returns -1 for negative numbers, 0 otherwise,
   246  // interpreting x as an int of size bitsize.
   247  func signWithBitsize(x int64, bitsize uint) int64 {
   248  	return (x << (64 - bitsize)) >> 63
   249  }
   250  
   251  func (l Limit) String() string {
   252  	return fmt.Sprintf("sm,SM=%d,%d um,UM=%d,%d", l.Min, l.Max, l.Umin, l.Umax)
   253  }
   254  
   255  func (l Limit) Intersect(l2 Limit) Limit {
   256  	l.Min = max(l.Min, l2.Min)
   257  	l.Umin = max(l.Umin, l2.Umin)
   258  	l.Max = min(l.Max, l2.Max)
   259  	l.Umax = min(l.Umax, l2.Umax)
   260  	return l
   261  }
   262  
   263  func (l Limit) signedMin(m int64) Limit {
   264  	l.Min = max(l.Min, m)
   265  	return l
   266  }
   267  
   268  func (l Limit) SignedMinMax(minimum, maximum int64) Limit {
   269  	l.Min = max(l.Min, minimum)
   270  	l.Max = min(l.Max, maximum)
   271  	return l
   272  }
   273  
   274  func (l Limit) UnsignedMin(m uint64) Limit {
   275  	l.Umin = max(l.Umin, m)
   276  	return l
   277  }
   278  
   279  func (l Limit) UnsignedMax(m uint64) Limit {
   280  	l.Umax = min(l.Umax, m)
   281  	return l
   282  }
   283  
   284  func (l Limit) UnsignedMinMax(minimum, maximum uint64) Limit {
   285  	l.Umin = max(l.Umin, minimum)
   286  	l.Umax = min(l.Umax, maximum)
   287  	return l
   288  }
   289  
   290  func (l Limit) nonzero() bool {
   291  	return l.Min > 0 || l.Umin > 0 || l.Max < 0
   292  }
   293  
   294  func (l Limit) MaybeZero() bool {
   295  	return !l.nonzero()
   296  }
   297  
   298  func (l Limit) Nonnegative() bool {
   299  	return l.Min >= 0
   300  }
   301  
   302  func (l Limit) Unsat() bool {
   303  	return l.Min > l.Max || l.Umin > l.Umax
   304  }
   305  
   306  // UnsignedFixedLeadingBits extracts the all the most significant fixed bits from the limit.
   307  // fixed and count are an other way to represent a limit, you can convert them to a limit as follows:
   308  //
   309  //	umin = fixed
   310  //	umax = fixed | (1<<(64-count) - 1)
   311  //
   312  // In order to be useful for bitmanip analysis fixed and count are a coarser tool than a limit:
   313  // 1. the varying section (umax-umin) is always one less than a power of two
   314  // 2. that section is naturally aligned inside the 64-bit space
   315  func (l Limit) UnsignedFixedLeadingBits() (fixed uint64, count uint) {
   316  	varying := uint(bits.Len64(l.Umin ^ l.Umax))
   317  	count = uint(bits.LeadingZeros64(l.Umin ^ l.Umax))
   318  	fixed = l.Umin &^ (1<<varying - 1)
   319  	return
   320  }
   321  
   322  // Add returns the limit obtained by adding a value with limit l
   323  // to a value with limit l2. The result must fit in b bits.
   324  func (l Limit) Add(l2 Limit, b uint) Limit {
   325  	var isLConst, isL2Const bool
   326  	var lConst, l2Const uint64
   327  	if l.Min == l.Max {
   328  		isLConst = true
   329  		lConst = ConvertIntWithBitsize[uint64](l.Min, b)
   330  	} else if l.Umin == l.Umax {
   331  		isLConst = true
   332  		lConst = l.Umin
   333  	}
   334  	if l2.Min == l2.Max {
   335  		isL2Const = true
   336  		l2Const = ConvertIntWithBitsize[uint64](l2.Min, b)
   337  	} else if l2.Umin == l2.Umax {
   338  		isL2Const = true
   339  		l2Const = l2.Umin
   340  	}
   341  	if isLConst && isL2Const {
   342  		r := lConst + l2Const
   343  		r &= (uint64(1) << b) - 1
   344  		int64r := ConvertIntWithBitsize[int64](r, b)
   345  		return Limit{Min: int64r, Max: int64r, Umin: r, Umax: r}
   346  	}
   347  
   348  	r := NoLimit()
   349  	min, minOk := SafeAdd(l.Min, l2.Min, b)
   350  	max, maxOk := SafeAdd(l.Max, l2.Max, b)
   351  	if minOk && maxOk {
   352  		r.Min = min
   353  		r.Max = max
   354  	}
   355  	umin, uminOk := safeAddU(l.Umin, l2.Umin, b)
   356  	umax, umaxOk := safeAddU(l.Umax, l2.Umax, b)
   357  	if uminOk && umaxOk {
   358  		r.Umin = umin
   359  		r.Umax = umax
   360  	}
   361  	return r
   362  }
   363  
   364  // same as add but for subtraction.
   365  func (l Limit) Sub(l2 Limit, b uint) Limit {
   366  	r := NoLimit()
   367  	min, minOk := SafeSub(l.Min, l2.Max, b)
   368  	max, maxOk := SafeSub(l.Max, l2.Min, b)
   369  	if minOk && maxOk {
   370  		r.Min = min
   371  		r.Max = max
   372  	}
   373  	umin, uminOk := SafeSubU(l.Umin, l2.Umax, b)
   374  	umax, umaxOk := SafeSubU(l.Umax, l2.Umin, b)
   375  	if uminOk && umaxOk {
   376  		r.Umin = umin
   377  		r.Umax = umax
   378  	}
   379  	return r
   380  }
   381  
   382  // same as add but for multiplication.
   383  func (l Limit) Mul(l2 Limit, b uint) Limit {
   384  	r := NoLimit()
   385  	umaxhi, umaxlo := bits.Mul64(l.Umax, l2.Umax)
   386  	if umaxhi == 0 && FitsInBitsU(umaxlo, b) {
   387  		r.Umax = umaxlo
   388  		r.Umin = l.Umin * l2.Umin
   389  		// Note: if the code containing this multiply is
   390  		// unreachable, then we may have umin>umax, and this
   391  		// multiply may overflow.  But that's ok for
   392  		// unreachable code. If this code is reachable, we
   393  		// know umin<=umax, so this multiply will not overflow
   394  		// because the max multiply didn't.
   395  	}
   396  	// Signed is harder, so don't bother. The only useful
   397  	// case is when we know both multiplicands are nonnegative,
   398  	// but that case is handled above because we would have then
   399  	// previously propagated signed info to the unsigned domain,
   400  	// and will propagate it back after the multiply.
   401  	return r
   402  }
   403  
   404  // Similar to add, but compute 1 << l if it fits without overflow in b bits.
   405  func (l Limit) Exp2(b uint) Limit {
   406  	r := NoLimit()
   407  	if l.Umax < uint64(b) {
   408  		r.Umin = 1 << l.Umin
   409  		r.Umax = 1 << l.Umax
   410  		// Same as above in mul, signed<->unsigned propagation
   411  		// will handle the signed case for us.
   412  	}
   413  	return r
   414  }
   415  
   416  // Similar to add, but computes the complement of the limit for bitsize b.
   417  func (l Limit) Com(b uint) Limit {
   418  	switch b {
   419  	case 64:
   420  		return Limit{
   421  			Min:  ^l.Max,
   422  			Max:  ^l.Min,
   423  			Umin: ^l.Umax,
   424  			Umax: ^l.Umin,
   425  		}
   426  	case 32:
   427  		return Limit{
   428  			Min:  int64(^int32(l.Max)),
   429  			Max:  int64(^int32(l.Min)),
   430  			Umin: uint64(^uint32(l.Umax)),
   431  			Umax: uint64(^uint32(l.Umin)),
   432  		}
   433  	case 16:
   434  		return Limit{
   435  			Min:  int64(^int16(l.Max)),
   436  			Max:  int64(^int16(l.Min)),
   437  			Umin: uint64(^uint16(l.Umax)),
   438  			Umax: uint64(^uint16(l.Umin)),
   439  		}
   440  	case 8:
   441  		return Limit{
   442  			Min:  int64(^int8(l.Max)),
   443  			Max:  int64(^int8(l.Min)),
   444  			Umin: uint64(^uint8(l.Umax)),
   445  			Umax: uint64(^uint8(l.Umin)),
   446  		}
   447  	default:
   448  		panic("unreachable")
   449  	}
   450  }
   451  
   452  // Similar to add, but computes the negation of the limit for bitsize b.
   453  func (l Limit) Neg(b uint) Limit {
   454  	return l.Com(b).Add(Limit{Min: 1, Max: 1, Umin: 1, Umax: 1}, b)
   455  }
   456  
   457  // Similar to add, but computes the TrailingZeros of the limit for bitsize b.
   458  func (l Limit) Ctz(b uint) Limit {
   459  	fixed, fixedCount := l.UnsignedFixedLeadingBits()
   460  	if fixedCount == 64 {
   461  		constResult := min(uint(bits.TrailingZeros64(fixed)), b)
   462  		return Limit{Min: int64(constResult), Max: int64(constResult), Umin: uint64(constResult), Umax: uint64(constResult)}
   463  	}
   464  
   465  	varying := 64 - fixedCount
   466  	if l.Umin&((1<<varying)-1) != 0 {
   467  		// there will always be at least one non-zero bit in the varying part
   468  		varying--
   469  		return NoLimit().UnsignedMax(uint64(varying))
   470  	}
   471  	return NoLimit().UnsignedMax(uint64(min(uint(bits.TrailingZeros64(fixed)), b)))
   472  }
   473  
   474  // Similar to add, but computes the Len of the limit for bitsize b.
   475  func (l Limit) Bitlen(b uint) Limit {
   476  	return NoLimit().UnsignedMinMax(
   477  		uint64(bits.Len64(l.Umin)),
   478  		uint64(bits.Len64(l.Umax)),
   479  	)
   480  }
   481  
   482  // Similar to add, but computes the PopCount of the limit for bitsize b.
   483  func (l Limit) Popcount(b uint) Limit {
   484  	fixed, fixedCount := l.UnsignedFixedLeadingBits()
   485  	varying := 64 - fixedCount
   486  	fixedContribution := uint64(bits.OnesCount64(fixed))
   487  
   488  	min := fixedContribution
   489  	max := fixedContribution + uint64(varying)
   490  
   491  	varyingMask := uint64(1)<<varying - 1
   492  
   493  	if varyingPartOfUmax := l.Umax & varyingMask; uint(bits.OnesCount64(varyingPartOfUmax)) != varying {
   494  		// there is at least one zero bit in the varying part
   495  		max--
   496  	}
   497  	if varyingPartOfUmin := l.Umin & varyingMask; varyingPartOfUmin != 0 {
   498  		// there is at least one non-zero bit in the varying part
   499  		min++
   500  	}
   501  
   502  	return NoLimit().UnsignedMinMax(min, max)
   503  }
   504  
   505  func (l Limit) ConstValue() (_ int64, ok bool) {
   506  	switch {
   507  	case l.Min == l.Max:
   508  		return l.Min, true
   509  	case l.Umin == l.Umax:
   510  		return int64(l.Umin), true
   511  	default:
   512  		return 0, false
   513  	}
   514  }
   515
View as plain text