Source file src/cmd/compile/internal/ssa/rewrite.go

     1  // Copyright 2015 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/base"
     9  	"cmd/compile/internal/ir"
    10  	"cmd/compile/internal/logopt"
    11  	"cmd/compile/internal/reflectdata"
    12  	"cmd/compile/internal/rttype"
    13  	"cmd/compile/internal/typecheck"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/obj"
    16  	"cmd/internal/obj/s390x"
    17  	"cmd/internal/objabi"
    18  	"cmd/internal/src"
    19  	"encoding/binary"
    20  	"fmt"
    21  	"internal/buildcfg"
    22  	"io"
    23  	"math"
    24  	"math/bits"
    25  	"os"
    26  	"path/filepath"
    27  	"strings"
    28  )
    29  
    30  type deadValueChoice bool
    31  
    32  const (
    33  	leaveDeadValues  deadValueChoice = false
    34  	removeDeadValues                 = true
    35  
    36  	repZeroThreshold = 1408 // size beyond which we use REP STOS for zeroing
    37  	repMoveThreshold = 1408 // size beyond which we use REP MOVS for copying
    38  )
    39  
    40  // deadcode indicates whether rewrite should try to remove any values that become dead.
    41  func applyRewrite(f *Func, rb blockRewriter, rv valueRewriter, deadcode deadValueChoice) {
    42  	// repeat rewrites until we find no more rewrites
    43  	pendingLines := f.cachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
    44  	pendingLines.clear()
    45  	debug := f.pass.debug
    46  	if debug > 1 {
    47  		fmt.Printf("%s: rewriting for %s\n", f.pass.name, f.Name)
    48  	}
    49  	// if the number of rewrite iterations reaches itersLimit we will
    50  	// at that point turn on cycle detection. Instead of a fixed limit,
    51  	// size the limit according to func size to allow for cases such
    52  	// as the one in issue #66773.
    53  	itersLimit := f.NumBlocks()
    54  	if itersLimit < 20 {
    55  		itersLimit = 20
    56  	}
    57  	var iters int
    58  	var states map[string]bool
    59  	for {
    60  		if debug > 1 {
    61  			fmt.Printf("%s: iter %d\n", f.pass.name, iters)
    62  		}
    63  		change := false
    64  		deadChange := false
    65  		for _, b := range f.Blocks {
    66  			var b0 *Block
    67  			if debug > 1 {
    68  				fmt.Printf("%s: start block\n", f.pass.name)
    69  				b0 = new(Block)
    70  				*b0 = *b
    71  				b0.Succs = append([]Edge{}, b.Succs...) // make a new copy, not aliasing
    72  			}
    73  			for i, c := range b.ControlValues() {
    74  				for c.Op == OpCopy {
    75  					c = c.Args[0]
    76  					b.ReplaceControl(i, c)
    77  				}
    78  			}
    79  			if rb(b) {
    80  				change = true
    81  				if debug > 1 {
    82  					fmt.Printf("rewriting %s  ->  %s\n", b0.LongString(), b.LongString())
    83  				}
    84  			}
    85  			for j, v := range b.Values {
    86  				if debug > 1 {
    87  					fmt.Printf("%s: consider %v\n", f.pass.name, v.LongString())
    88  				}
    89  				var v0 *Value
    90  				if debug > 1 {
    91  					v0 = new(Value)
    92  					*v0 = *v
    93  					v0.Args = append([]*Value{}, v.Args...) // make a new copy, not aliasing
    94  				}
    95  				if v.Uses == 0 && v.removeable() {
    96  					if v.Op != OpInvalid && deadcode == removeDeadValues {
    97  						// Reset any values that are now unused, so that we decrement
    98  						// the use count of all of its arguments.
    99  						// Not quite a deadcode pass, because it does not handle cycles.
   100  						// But it should help Uses==1 rules to fire.
   101  						v.reset(OpInvalid)
   102  						deadChange = true
   103  					}
   104  					// No point rewriting values which aren't used.
   105  					continue
   106  				}
   107  
   108  				vchange := phielimValue(v)
   109  				if vchange && debug > 1 {
   110  					fmt.Printf("rewriting %s  ->  %s\n", v0.LongString(), v.LongString())
   111  				}
   112  
   113  				// Eliminate copy inputs.
   114  				// If any copy input becomes unused, mark it
   115  				// as invalid and discard its argument. Repeat
   116  				// recursively on the discarded argument.
   117  				// This phase helps remove phantom "dead copy" uses
   118  				// of a value so that a x.Uses==1 rule condition
   119  				// fires reliably.
   120  				for i, a := range v.Args {
   121  					if a.Op != OpCopy {
   122  						continue
   123  					}
   124  					aa := copySource(a)
   125  					v.SetArg(i, aa)
   126  					// If a, a copy, has a line boundary indicator, attempt to find a new value
   127  					// to hold it.  The first candidate is the value that will replace a (aa),
   128  					// if it shares the same block and line and is eligible.
   129  					// The second option is v, which has a as an input.  Because aa is earlier in
   130  					// the data flow, it is the better choice.
   131  					if a.Pos.IsStmt() == src.PosIsStmt {
   132  						if aa.Block == a.Block && aa.Pos.Line() == a.Pos.Line() && aa.Pos.IsStmt() != src.PosNotStmt {
   133  							aa.Pos = aa.Pos.WithIsStmt()
   134  						} else if v.Block == a.Block && v.Pos.Line() == a.Pos.Line() && v.Pos.IsStmt() != src.PosNotStmt {
   135  							v.Pos = v.Pos.WithIsStmt()
   136  						} else {
   137  							// Record the lost line and look for a new home after all rewrites are complete.
   138  							// TODO: it's possible (in FOR loops, in particular) for statement boundaries for the same
   139  							// line to appear in more than one block, but only one block is stored, so if both end
   140  							// up here, then one will be lost.
   141  							pendingLines.set(a.Pos, int32(a.Block.ID))
   142  						}
   143  						a.Pos = a.Pos.WithNotStmt()
   144  					}
   145  					vchange = true
   146  					for a.Uses == 0 {
   147  						b := a.Args[0]
   148  						a.reset(OpInvalid)
   149  						a = b
   150  					}
   151  				}
   152  				if vchange && debug > 1 {
   153  					fmt.Printf("rewriting %s  ->  %s\n", v0.LongString(), v.LongString())
   154  				}
   155  
   156  				// apply rewrite function
   157  				if rv(v) {
   158  					vchange = true
   159  					// If value changed to a poor choice for a statement boundary, move the boundary
   160  					if v.Pos.IsStmt() == src.PosIsStmt {
   161  						if k := nextGoodStatementIndex(v, j, b); k != j {
   162  							v.Pos = v.Pos.WithNotStmt()
   163  							b.Values[k].Pos = b.Values[k].Pos.WithIsStmt()
   164  						}
   165  					}
   166  				}
   167  
   168  				change = change || vchange
   169  				if vchange && debug > 1 {
   170  					fmt.Printf("rewriting %s  ->  %s\n", v0.LongString(), v.LongString())
   171  				}
   172  			}
   173  		}
   174  		if !change && !deadChange {
   175  			break
   176  		}
   177  		iters++
   178  		if (iters > itersLimit || debug >= 2) && change {
   179  			// We've done a suspiciously large number of rewrites (or we're in debug mode).
   180  			// As of Sep 2021, 90% of rewrites complete in 4 iterations or fewer
   181  			// and the maximum value encountered during make.bash is 12.
   182  			// Start checking for cycles. (This is too expensive to do routinely.)
   183  			// Note: we avoid this path for deadChange-only iterations, to fix #51639.
   184  			if states == nil {
   185  				states = make(map[string]bool)
   186  			}
   187  			h := f.rewriteHash()
   188  			if _, ok := states[h]; ok {
   189  				// We've found a cycle.
   190  				// To diagnose it, set debug to 2 and start again,
   191  				// so that we'll print all rules applied until we complete another cycle.
   192  				// If debug is already >= 2, we've already done that, so it's time to crash.
   193  				if debug < 2 {
   194  					debug = 2
   195  					states = make(map[string]bool)
   196  				} else {
   197  					f.Fatalf("rewrite cycle detected")
   198  				}
   199  			}
   200  			states[h] = true
   201  		}
   202  	}
   203  	// remove clobbered values
   204  	for _, b := range f.Blocks {
   205  		j := 0
   206  		for i, v := range b.Values {
   207  			vl := v.Pos
   208  			if v.Op == OpInvalid {
   209  				if v.Pos.IsStmt() == src.PosIsStmt {
   210  					pendingLines.set(vl, int32(b.ID))
   211  				}
   212  				f.freeValue(v)
   213  				continue
   214  			}
   215  			if v.Pos.IsStmt() != src.PosNotStmt && !notStmtBoundary(v.Op) {
   216  				if pl, ok := pendingLines.get(vl); ok && pl == int32(b.ID) {
   217  					pendingLines.remove(vl)
   218  					v.Pos = v.Pos.WithIsStmt()
   219  				}
   220  			}
   221  			if i != j {
   222  				b.Values[j] = v
   223  			}
   224  			j++
   225  		}
   226  		if pl, ok := pendingLines.get(b.Pos); ok && pl == int32(b.ID) {
   227  			b.Pos = b.Pos.WithIsStmt()
   228  			pendingLines.remove(b.Pos)
   229  		}
   230  		b.truncateValues(j)
   231  	}
   232  }
   233  
   234  // Common functions called from rewriting rules
   235  
   236  func is64BitFloat(t *types.Type) bool {
   237  	return t.Size() == 8 && t.IsFloat()
   238  }
   239  
   240  func is32BitFloat(t *types.Type) bool {
   241  	return t.Size() == 4 && t.IsFloat()
   242  }
   243  
   244  func is64BitInt(t *types.Type) bool {
   245  	return t.Size() == 8 && t.IsInteger()
   246  }
   247  
   248  func is32BitInt(t *types.Type) bool {
   249  	return t.Size() == 4 && t.IsInteger()
   250  }
   251  
   252  func is16BitInt(t *types.Type) bool {
   253  	return t.Size() == 2 && t.IsInteger()
   254  }
   255  
   256  func is8BitInt(t *types.Type) bool {
   257  	return t.Size() == 1 && t.IsInteger()
   258  }
   259  
   260  func isPtr(t *types.Type) bool {
   261  	return t.IsPtrShaped()
   262  }
   263  
   264  func copyCompatibleType(t1, t2 *types.Type) bool {
   265  	if t1.Size() != t2.Size() {
   266  		return false
   267  	}
   268  	if t1.IsInteger() {
   269  		return t2.IsInteger()
   270  	}
   271  	if isPtr(t1) {
   272  		return isPtr(t2)
   273  	}
   274  	return t1.Compare(t2) == types.CMPeq
   275  }
   276  
   277  // mergeSym merges two symbolic offsets. There is no real merging of
   278  // offsets, we just pick the non-nil one.
   279  func mergeSym(x, y Sym) Sym {
   280  	if x == nil {
   281  		return y
   282  	}
   283  	if y == nil {
   284  		return x
   285  	}
   286  	panic(fmt.Sprintf("mergeSym with two non-nil syms %v %v", x, y))
   287  }
   288  
   289  func canMergeSym(x, y Sym) bool {
   290  	return x == nil || y == nil
   291  }
   292  
   293  // canMergeLoadClobber reports whether the load can be merged into target without
   294  // invalidating the schedule.
   295  // It also checks that the other non-load argument x is something we
   296  // are ok with clobbering.
   297  func canMergeLoadClobber(target, load, x *Value) bool {
   298  	// The register containing x is going to get clobbered.
   299  	// Don't merge if we still need the value of x.
   300  	// We don't have liveness information here, but we can
   301  	// approximate x dying with:
   302  	//  1) target is x's only use.
   303  	//  2) target is not in a deeper loop than x.
   304  	switch {
   305  	case x.Uses == 2 && x.Op == OpPhi && len(x.Args) == 2 && (x.Args[0] == target || x.Args[1] == target) && target.Uses == 1:
   306  		// This is a simple detector to determine that x is probably
   307  		// not live after target. (It does not need to be perfect,
   308  		// regalloc will issue a reg-reg move to save it if we are wrong.)
   309  		// We have:
   310  		//   x = Phi(?, target)
   311  		//   target = Op(load, x)
   312  		// Because target has only one use as a Phi argument, we can schedule it
   313  		// very late. Hopefully, later than the other use of x. (The other use died
   314  		// between x and target, or exists on another branch entirely).
   315  	case x.Uses > 1:
   316  		return false
   317  	}
   318  	loopnest := x.Block.Func.loopnest()
   319  	if loopnest.depth(target.Block.ID) > loopnest.depth(x.Block.ID) {
   320  		return false
   321  	}
   322  	return canMergeLoad(target, load)
   323  }
   324  
   325  // canMergeLoad reports whether the load can be merged into target without
   326  // invalidating the schedule.
   327  func canMergeLoad(target, load *Value) bool {
   328  	if target.Block.ID != load.Block.ID {
   329  		// If the load is in a different block do not merge it.
   330  		return false
   331  	}
   332  
   333  	// We can't merge the load into the target if the load
   334  	// has more than one use.
   335  	if load.Uses != 1 {
   336  		return false
   337  	}
   338  
   339  	mem := load.MemoryArg()
   340  
   341  	// We need the load's memory arg to still be alive at target. That
   342  	// can't be the case if one of target's args depends on a memory
   343  	// state that is a successor of load's memory arg.
   344  	//
   345  	// For example, it would be invalid to merge load into target in
   346  	// the following situation because newmem has killed oldmem
   347  	// before target is reached:
   348  	//     load = read ... oldmem
   349  	//   newmem = write ... oldmem
   350  	//     arg0 = read ... newmem
   351  	//   target = add arg0 load
   352  	//
   353  	// If the argument comes from a different block then we can exclude
   354  	// it immediately because it must dominate load (which is in the
   355  	// same block as target).
   356  	var args []*Value
   357  	for _, a := range target.Args {
   358  		if a != load && a.Block.ID == target.Block.ID {
   359  			args = append(args, a)
   360  		}
   361  	}
   362  
   363  	f := target.Block.Func
   364  	visited := f.newSparseSet(f.NumValues())
   365  	defer f.retSparseSet(visited)
   366  
   367  	// memPreds contains memory states known to be predecessors of load's
   368  	// memory state. It is lazily initialized.
   369  	var memPreds map[*Value]bool
   370  	for len(args) > 0 {
   371  		const limit = 2048 // enough to comfortably cover unrolled crypto blocks
   372  		if visited.size() >= limit {
   373  			// Give up if we have visited a lot of values.
   374  			return false
   375  		}
   376  		v := args[len(args)-1]
   377  		args = args[:len(args)-1]
   378  		if visited.contains(v.ID) {
   379  			continue
   380  		}
   381  		visited.add(v.ID)
   382  		if target.Block.ID != v.Block.ID {
   383  			// Since target and load are in the same block
   384  			// we can stop searching when we leave the block.
   385  			continue
   386  		}
   387  		if v.Op == OpPhi {
   388  			// A Phi implies we have reached the top of the block.
   389  			// The memory phi, if it exists, is always
   390  			// the first logical store in the block.
   391  			continue
   392  		}
   393  		if v.Type.IsTuple() && v.Type.FieldType(1).IsMemory() {
   394  			// We could handle this situation however it is likely
   395  			// to be very rare.
   396  			return false
   397  		}
   398  		if v.Op.SymEffect()&SymAddr != 0 {
   399  			// This case prevents an operation that calculates the
   400  			// address of a local variable from being forced to schedule
   401  			// before its corresponding VarDef.
   402  			// See issue 28445.
   403  			//   v1 = LOAD ...
   404  			//   v2 = VARDEF
   405  			//   v3 = LEAQ
   406  			//   v4 = CMPQ v1 v3
   407  			// We don't want to combine the CMPQ with the load, because
   408  			// that would force the CMPQ to schedule before the VARDEF, which
   409  			// in turn requires the LEAQ to schedule before the VARDEF.
   410  			return false
   411  		}
   412  		if v.Type.IsMemory() {
   413  			if memPreds == nil {
   414  				// Initialise a map containing memory states
   415  				// known to be predecessors of load's memory
   416  				// state.
   417  				memPreds = make(map[*Value]bool)
   418  				m := mem
   419  				const limit = 50
   420  				for i := 0; i < limit; i++ {
   421  					if m.Op == OpPhi {
   422  						// The memory phi, if it exists, is always
   423  						// the first logical store in the block.
   424  						break
   425  					}
   426  					if m.Block.ID != target.Block.ID {
   427  						break
   428  					}
   429  					if !m.Type.IsMemory() {
   430  						break
   431  					}
   432  					memPreds[m] = true
   433  					if len(m.Args) == 0 {
   434  						break
   435  					}
   436  					m = m.MemoryArg()
   437  				}
   438  			}
   439  
   440  			// We can merge if v is a predecessor of mem.
   441  			//
   442  			// For example, we can merge load into target in the
   443  			// following scenario:
   444  			//      x = read ... v
   445  			//    mem = write ... v
   446  			//   load = read ... mem
   447  			// target = add x load
   448  			if memPreds[v] {
   449  				continue
   450  			}
   451  			return false
   452  		}
   453  		if len(v.Args) > 0 && v.Args[len(v.Args)-1] == mem {
   454  			// If v takes mem as an input then we know mem
   455  			// is valid at this point.
   456  			continue
   457  		}
   458  		for _, a := range v.Args {
   459  			if target.Block.ID == a.Block.ID {
   460  				args = append(args, a)
   461  			}
   462  		}
   463  	}
   464  
   465  	return true
   466  }
   467  
   468  // isSameCall reports whether aux is the same as the given named symbol.
   469  func isSameCall(aux Aux, name string) bool {
   470  	fn := aux.(*AuxCall).Fn
   471  	return fn != nil && fn.String() == name
   472  }
   473  
   474  func isMalloc(aux Aux) bool {
   475  	return isNewObject(aux) || isSpecializedMalloc(aux)
   476  }
   477  
   478  func isNewObject(aux Aux) bool {
   479  	fn := aux.(*AuxCall).Fn
   480  	return fn != nil && fn.String() == "runtime.newobject"
   481  }
   482  
   483  func isSpecializedMalloc(aux Aux) bool {
   484  	fn := aux.(*AuxCall).Fn
   485  	if fn == nil {
   486  		return false
   487  	}
   488  	name := fn.String()
   489  	return strings.HasPrefix(name, "runtime.mallocgcSmallNoScanSC") ||
   490  		strings.HasPrefix(name, "runtime.mallocgcSmallScanNoHeaderSC") ||
   491  		strings.HasPrefix(name, "runtime.mallocgcTinySC")
   492  }
   493  
   494  // canLoadUnaligned reports if the architecture supports unaligned load operations.
   495  func canLoadUnaligned(c *Config) bool {
   496  	return c.ctxt.Arch.Alignment == 1
   497  }
   498  
   499  // nlzX returns the number of leading zeros.
   500  func nlz64(x int64) int { return bits.LeadingZeros64(uint64(x)) }
   501  func nlz32(x int32) int { return bits.LeadingZeros32(uint32(x)) }
   502  func nlz16(x int16) int { return bits.LeadingZeros16(uint16(x)) }
   503  func nlz8(x int8) int   { return bits.LeadingZeros8(uint8(x)) }
   504  
   505  // ntzX returns the number of trailing zeros.
   506  func ntz64(x int64) int { return bits.TrailingZeros64(uint64(x)) }
   507  func ntz32(x int32) int { return bits.TrailingZeros32(uint32(x)) }
   508  func ntz16(x int16) int { return bits.TrailingZeros16(uint16(x)) }
   509  func ntz8(x int8) int   { return bits.TrailingZeros8(uint8(x)) }
   510  
   511  // oneBit reports whether x contains exactly one set bit.
   512  func oneBit[T int8 | int16 | int32 | int64](x T) bool {
   513  	return x&(x-1) == 0 && x != 0
   514  }
   515  
   516  // nto returns the number of trailing ones.
   517  func nto(x int64) int64 {
   518  	return int64(ntz64(^x))
   519  }
   520  
   521  // logX returns logarithm of n base 2.
   522  // n must be a positive power of 2 (isPowerOfTwoX returns true).
   523  func log8(n int8) int64   { return log8u(uint8(n)) }
   524  func log16(n int16) int64 { return log16u(uint16(n)) }
   525  func log32(n int32) int64 { return log32u(uint32(n)) }
   526  func log64(n int64) int64 { return log64u(uint64(n)) }
   527  
   528  // logXu returns the logarithm of n base 2.
   529  // n must be a power of 2 (isPowerOfTwo returns true)
   530  func log8u(n uint8) int64   { return int64(bits.Len8(n)) - 1 }
   531  func log16u(n uint16) int64 { return int64(bits.Len16(n)) - 1 }
   532  func log32u(n uint32) int64 { return int64(bits.Len32(n)) - 1 }
   533  func log64u(n uint64) int64 { return int64(bits.Len64(n)) - 1 }
   534  
   535  // isPowerOfTwoX functions report whether n is a power of 2.
   536  func isPowerOfTwo[T int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64](n T) bool {
   537  	return n > 0 && n&(n-1) == 0
   538  }
   539  
   540  // is32Bit reports whether n can be represented as a signed 32 bit integer.
   541  func is32Bit(n int64) bool {
   542  	return n == int64(int32(n))
   543  }
   544  
   545  // is16Bit reports whether n can be represented as a signed 16 bit integer.
   546  func is16Bit(n int64) bool {
   547  	return n == int64(int16(n))
   548  }
   549  
   550  // is8Bit reports whether n can be represented as a signed 8 bit integer.
   551  func is8Bit(n int64) bool {
   552  	return n == int64(int8(n))
   553  }
   554  
   555  // isU8Bit reports whether n can be represented as an unsigned 8 bit integer.
   556  func isU8Bit(n int64) bool {
   557  	return n == int64(uint8(n))
   558  }
   559  
   560  // is12Bit reports whether n can be represented as a signed 12 bit integer.
   561  func is12Bit(n int64) bool {
   562  	return -(1<<11) <= n && n < (1<<11)
   563  }
   564  
   565  // isU12Bit reports whether n can be represented as an unsigned 12 bit integer.
   566  func isU12Bit(n int64) bool {
   567  	return 0 <= n && n < (1<<12)
   568  }
   569  
   570  // isU16Bit reports whether n can be represented as an unsigned 16 bit integer.
   571  func isU16Bit(n int64) bool {
   572  	return n == int64(uint16(n))
   573  }
   574  
   575  // isU32Bit reports whether n can be represented as an unsigned 32 bit integer.
   576  func isU32Bit(n int64) bool {
   577  	return n == int64(uint32(n))
   578  }
   579  
   580  // is20Bit reports whether n can be represented as a signed 20 bit integer.
   581  func is20Bit(n int64) bool {
   582  	return -(1<<19) <= n && n < (1<<19)
   583  }
   584  
   585  // b2i translates a boolean value to 0 or 1 for assigning to auxInt.
   586  func b2i(b bool) int64 {
   587  	if b {
   588  		return 1
   589  	}
   590  	return 0
   591  }
   592  
   593  // b2i32 translates a boolean value to 0 or 1.
   594  func b2i32(b bool) int32 {
   595  	if b {
   596  		return 1
   597  	}
   598  	return 0
   599  }
   600  
   601  func canMulStrengthReduce(config *Config, x int64) bool {
   602  	_, ok := config.mulRecipes[x]
   603  	return ok
   604  }
   605  func canMulStrengthReduce32(config *Config, x int32) bool {
   606  	_, ok := config.mulRecipes[int64(x)]
   607  	return ok
   608  }
   609  
   610  // mulStrengthReduce returns v*x evaluated at the location
   611  // (block and source position) of m.
   612  // canMulStrengthReduce must have returned true.
   613  func mulStrengthReduce(m *Value, v *Value, x int64) *Value {
   614  	return v.Block.Func.Config.mulRecipes[x].build(m, v)
   615  }
   616  
   617  // mulStrengthReduce32 returns v*x evaluated at the location
   618  // (block and source position) of m.
   619  // canMulStrengthReduce32 must have returned true.
   620  // The upper 32 bits of m might be set to junk.
   621  func mulStrengthReduce32(m *Value, v *Value, x int32) *Value {
   622  	return v.Block.Func.Config.mulRecipes[int64(x)].build(m, v)
   623  }
   624  
   625  // shiftIsBounded reports whether (left/right) shift Value v is known to be bounded.
   626  // A shift is bounded if it is shifting by less than the width of the shifted value.
   627  func shiftIsBounded(v *Value) bool {
   628  	return v.AuxInt != 0
   629  }
   630  
   631  // canonLessThan returns whether x is "ordered" less than y, for purposes of normalizing
   632  // generated code as much as possible.
   633  func canonLessThan(x, y *Value) bool {
   634  	if x.Op != y.Op {
   635  		return x.Op < y.Op
   636  	}
   637  	if !x.Pos.SameFileAndLine(y.Pos) {
   638  		return x.Pos.Before(y.Pos)
   639  	}
   640  	return x.ID < y.ID
   641  }
   642  
   643  // truncate64Fto32F converts a float64 value to a float32 preserving the bit pattern
   644  // of the mantissa. It will panic if the truncation results in lost information.
   645  func truncate64Fto32F(f float64) float32 {
   646  	if !isExactFloat32(f) {
   647  		panic("truncate64Fto32F: truncation is not exact")
   648  	}
   649  	if !math.IsNaN(f) {
   650  		return float32(f)
   651  	}
   652  	// NaN bit patterns aren't necessarily preserved across conversion
   653  	// instructions so we need to do the conversion manually.
   654  	b := math.Float64bits(f)
   655  	m := b & ((1 << 52) - 1) // mantissa (a.k.a. significand)
   656  	//          | sign                  | exponent   | mantissa       |
   657  	r := uint32(((b >> 32) & (1 << 31)) | 0x7f800000 | (m >> (52 - 23)))
   658  	return math.Float32frombits(r)
   659  }
   660  
   661  // DivisionNeedsFixUp reports whether the division needs fix-up code.
   662  func DivisionNeedsFixUp(v *Value) bool {
   663  	return v.AuxInt == 0
   664  }
   665  
   666  // auxTo32F decodes a float32 from the AuxInt value provided.
   667  func auxTo32F(i int64) float32 {
   668  	return truncate64Fto32F(math.Float64frombits(uint64(i)))
   669  }
   670  
   671  func auxIntToBool(i int64) bool {
   672  	if i == 0 {
   673  		return false
   674  	}
   675  	return true
   676  }
   677  func auxIntToInt8(i int64) int8 {
   678  	return int8(i)
   679  }
   680  func auxIntToInt16(i int64) int16 {
   681  	return int16(i)
   682  }
   683  func auxIntToInt32(i int64) int32 {
   684  	return int32(i)
   685  }
   686  func auxIntToInt64(i int64) int64 {
   687  	return i
   688  }
   689  func auxIntToUint8(i int64) uint8 {
   690  	return uint8(i)
   691  }
   692  func auxIntToUint64(i int64) uint64 {
   693  	return uint64(i)
   694  }
   695  func auxIntToFloat32(i int64) float32 {
   696  	return float32(math.Float64frombits(uint64(i)))
   697  }
   698  func auxIntToFloat64(i int64) float64 {
   699  	return math.Float64frombits(uint64(i))
   700  }
   701  func auxIntToValAndOff(i int64) ValAndOff {
   702  	return ValAndOff(i)
   703  }
   704  func auxIntToArm64BitField(i int64) arm64BitField {
   705  	return arm64BitField(i)
   706  }
   707  func auxIntToArm64ConditionalParams(i int64) arm64ConditionalParams {
   708  	var params arm64ConditionalParams
   709  	params.cond = Op(i & 0xffff)
   710  	i >>= 16
   711  	params.nzcv = uint8(i & 0x0f)
   712  	i >>= 4
   713  	params.constValue = uint8(i & 0x1f)
   714  	i >>= 5
   715  	params.ind = i == 1
   716  	return params
   717  }
   718  func auxIntToFlagConstant(x int64) flagConstant {
   719  	return flagConstant(x)
   720  }
   721  
   722  func auxIntToOp(cc int64) Op {
   723  	return Op(cc)
   724  }
   725  
   726  func boolToAuxInt(b bool) int64 {
   727  	if b {
   728  		return 1
   729  	}
   730  	return 0
   731  }
   732  func int8ToAuxInt(i int8) int64 {
   733  	return int64(i)
   734  }
   735  func int16ToAuxInt(i int16) int64 {
   736  	return int64(i)
   737  }
   738  func int32ToAuxInt(i int32) int64 {
   739  	return int64(i)
   740  }
   741  func int64ToAuxInt(i int64) int64 {
   742  	return i
   743  }
   744  func uint8ToAuxInt(i uint8) int64 {
   745  	return int64(int8(i))
   746  }
   747  func uint64ToAuxInt(i uint64) int64 {
   748  	return int64(i)
   749  }
   750  func float32ToAuxInt(f float32) int64 {
   751  	return int64(math.Float64bits(float64(f)))
   752  }
   753  func float64ToAuxInt(f float64) int64 {
   754  	return int64(math.Float64bits(f))
   755  }
   756  func valAndOffToAuxInt(v ValAndOff) int64 {
   757  	return int64(v)
   758  }
   759  func arm64BitFieldToAuxInt(v arm64BitField) int64 {
   760  	return int64(v)
   761  }
   762  func arm64ConditionalParamsToAuxInt(v arm64ConditionalParams) int64 {
   763  	if v.cond&^0xffff != 0 {
   764  		panic("condition value exceeds 16 bits")
   765  	}
   766  
   767  	var i int64
   768  	if v.ind {
   769  		i = 1 << 25
   770  	}
   771  	i |= int64(v.constValue) << 20
   772  	i |= int64(v.nzcv) << 16
   773  	i |= int64(v.cond)
   774  	return i
   775  }
   776  
   777  func flagConstantToAuxInt(x flagConstant) int64 {
   778  	return int64(x)
   779  }
   780  
   781  func opToAuxInt(o Op) int64 {
   782  	return int64(o)
   783  }
   784  
   785  // Aux is an interface to hold miscellaneous data in Blocks and Values.
   786  type Aux interface {
   787  	CanBeAnSSAAux()
   788  }
   789  
   790  // for now only used to mark moves that need to avoid clobbering flags
   791  type auxMark bool
   792  
   793  func (auxMark) CanBeAnSSAAux() {}
   794  
   795  var AuxMark auxMark
   796  
   797  // stringAux wraps string values for use in Aux.
   798  type stringAux string
   799  
   800  func (stringAux) CanBeAnSSAAux() {}
   801  
   802  func auxToString(i Aux) string {
   803  	return string(i.(stringAux))
   804  }
   805  func auxToSym(i Aux) Sym {
   806  	// TODO: kind of a hack - allows nil interface through
   807  	s, _ := i.(Sym)
   808  	return s
   809  }
   810  func auxToType(i Aux) *types.Type {
   811  	return i.(*types.Type)
   812  }
   813  func auxToCall(i Aux) *AuxCall {
   814  	return i.(*AuxCall)
   815  }
   816  func auxToS390xCCMask(i Aux) s390x.CCMask {
   817  	return i.(s390x.CCMask)
   818  }
   819  func auxToS390xRotateParams(i Aux) s390x.RotateParams {
   820  	return i.(s390x.RotateParams)
   821  }
   822  
   823  func StringToAux(s string) Aux {
   824  	return stringAux(s)
   825  }
   826  func symToAux(s Sym) Aux {
   827  	return s
   828  }
   829  func callToAux(s *AuxCall) Aux {
   830  	return s
   831  }
   832  func typeToAux(t *types.Type) Aux {
   833  	return t
   834  }
   835  func s390xCCMaskToAux(c s390x.CCMask) Aux {
   836  	return c
   837  }
   838  func s390xRotateParamsToAux(r s390x.RotateParams) Aux {
   839  	return r
   840  }
   841  
   842  // uaddOvf reports whether unsigned a+b would overflow.
   843  func uaddOvf(a, b int64) bool {
   844  	return uint64(a)+uint64(b) < uint64(a)
   845  }
   846  
   847  func devirtLECall(v *Value, sym *obj.LSym) *Value {
   848  	v.Op = OpStaticLECall
   849  	auxcall := v.Aux.(*AuxCall)
   850  	auxcall.Fn = sym
   851  	// Remove first arg
   852  	v.Args[0].Uses--
   853  	copy(v.Args[0:], v.Args[1:])
   854  	v.Args[len(v.Args)-1] = nil // aid GC
   855  	v.Args = v.Args[:len(v.Args)-1]
   856  	if f := v.Block.Func; f.pass.debug > 0 {
   857  		f.Warnl(v.Pos, "de-virtualizing call")
   858  	}
   859  	return v
   860  }
   861  
   862  // isSamePtr reports whether p1 and p2 point to the same address.
   863  func isSamePtr(p1, p2 *Value) bool {
   864  	if p1 == p2 {
   865  		return true
   866  	}
   867  	if p1.Op != p2.Op {
   868  		for p1.Op == OpOffPtr && p1.AuxInt == 0 {
   869  			p1 = p1.Args[0]
   870  		}
   871  		for p2.Op == OpOffPtr && p2.AuxInt == 0 {
   872  			p2 = p2.Args[0]
   873  		}
   874  		if p1 == p2 {
   875  			return true
   876  		}
   877  		if p1.Op != p2.Op {
   878  			return false
   879  		}
   880  	}
   881  	switch p1.Op {
   882  	case OpOffPtr:
   883  		return p1.AuxInt == p2.AuxInt && isSamePtr(p1.Args[0], p2.Args[0])
   884  	case OpAddr, OpLocalAddr:
   885  		return p1.Aux == p2.Aux
   886  	case OpAddPtr:
   887  		return p1.Args[1] == p2.Args[1] && isSamePtr(p1.Args[0], p2.Args[0])
   888  	}
   889  	return false
   890  }
   891  
   892  func isStackPtr(v *Value) bool {
   893  	for v.Op == OpOffPtr || v.Op == OpAddPtr {
   894  		v = v.Args[0]
   895  	}
   896  	return v.Op == OpSP || v.Op == OpLocalAddr
   897  }
   898  
   899  // disjoint reports whether the memory region specified by [p1:p1+t1.Size())
   900  // does not overlap with [p2:p2+t2.Size()).
   901  // A return value of false does not imply the regions overlap.
   902  func disjoint(p1 *Value, t1 *types.Type, p2 *Value, t2 *types.Type) bool {
   903  	return disjoint1(p1, t1.Size(), p2, t2.Size())
   904  }
   905  
   906  // disjoint1 reports whether the memory region specified by [p1:p1+n1)
   907  // does not overlap with [p2:p2+n2).
   908  // A return value of false does not imply the regions overlap.
   909  func disjoint1(p1 *Value, n1 int64, p2 *Value, n2 int64) bool {
   910  	if n1 == 0 || n2 == 0 {
   911  		return true
   912  	}
   913  	if p1 == p2 {
   914  		return false
   915  	}
   916  	baseAndOffset := func(ptr *Value) (base *Value, offset int64) {
   917  		base, offset = ptr, 0
   918  		for base.Op == OpOffPtr {
   919  			offset += base.AuxInt
   920  			base = base.Args[0]
   921  		}
   922  		if opcodeTable[base.Op].nilCheck {
   923  			base = base.Args[0]
   924  		}
   925  		return base, offset
   926  	}
   927  
   928  	// Run types-based analysis
   929  	if disjointTypes(p1.Type, p2.Type) {
   930  		return true
   931  	}
   932  
   933  	p1, off1 := baseAndOffset(p1)
   934  	p2, off2 := baseAndOffset(p2)
   935  	if isSamePtr(p1, p2) {
   936  		return !overlap(off1, n1, off2, n2)
   937  	}
   938  	// p1 and p2 are not the same, so if they are both OpAddrs then
   939  	// they point to different variables.
   940  	// If one pointer is on the stack and the other is an argument
   941  	// then they can't overlap.
   942  	switch p1.Op {
   943  	case OpAddr, OpLocalAddr:
   944  		if p2.Op == OpAddr || p2.Op == OpLocalAddr || p2.Op == OpSP {
   945  			return true
   946  		}
   947  		return (p2.Op == OpArg || p2.Op == OpArgIntReg) && p1.Args[0].Op == OpSP
   948  	case OpArg, OpArgIntReg:
   949  		if p2.Op == OpSP || p2.Op == OpLocalAddr {
   950  			return true
   951  		}
   952  	case OpSP:
   953  		return p2.Op == OpAddr || p2.Op == OpLocalAddr || p2.Op == OpArg || p2.Op == OpArgIntReg || p2.Op == OpSP
   954  	}
   955  	return false
   956  }
   957  
   958  // disjointTypes reports whether a memory region pointed to by a pointer of type
   959  // t1 does not overlap with a memory region pointed to by a pointer of type t2 --
   960  // based on type aliasing rules.
   961  func disjointTypes(t1 *types.Type, t2 *types.Type) bool {
   962  	// Unsafe pointer can alias with anything.
   963  	if t1.IsUnsafePtr() || t2.IsUnsafePtr() {
   964  		return false
   965  	}
   966  
   967  	if !t1.IsPtr() || !t2.IsPtr() {
   968  		// Treat non-pointer types (such as TFUNC, TMAP, uintptr) conservatively.
   969  		return false
   970  	}
   971  
   972  	t1 = t1.Elem()
   973  	t2 = t2.Elem()
   974  
   975  	// Not-in-heap types are not supported -- they are rare and non-important; also,
   976  	// type.HasPointers check doesn't work for them correctly.
   977  	if t1.NotInHeap() || t2.NotInHeap() {
   978  		return false
   979  	}
   980  
   981  	isPtrShaped := func(t *types.Type) bool { return int(t.Size()) == types.PtrSize && t.HasPointers() }
   982  
   983  	// Pointers and non-pointers are disjoint (https://pkg.go.dev/unsafe#Pointer).
   984  	if (isPtrShaped(t1) && !t2.HasPointers()) ||
   985  		(isPtrShaped(t2) && !t1.HasPointers()) {
   986  		return true
   987  	}
   988  
   989  	return false
   990  }
   991  
   992  // moveSize returns the number of bytes an aligned MOV instruction moves.
   993  func moveSize(align int64, c *Config) int64 {
   994  	switch {
   995  	case align%8 == 0 && c.PtrSize == 8:
   996  		return 8
   997  	case align%4 == 0:
   998  		return 4
   999  	case align%2 == 0:
  1000  		return 2
  1001  	}
  1002  	return 1
  1003  }
  1004  
  1005  // mergePoint finds a block among a's blocks which dominates b and is itself
  1006  // dominated by all of a's blocks. Returns nil if it can't find one.
  1007  // Might return nil even if one does exist.
  1008  func mergePoint(b *Block, a ...*Value) *Block {
  1009  	// Walk backward from b looking for one of the a's blocks.
  1010  
  1011  	// Max distance
  1012  	d := 100
  1013  
  1014  	for d > 0 {
  1015  		for _, x := range a {
  1016  			if b == x.Block {
  1017  				goto found
  1018  			}
  1019  		}
  1020  		if len(b.Preds) > 1 {
  1021  			// Don't know which way to go back. Abort.
  1022  			return nil
  1023  		}
  1024  		b = b.Preds[0].b
  1025  		d--
  1026  	}
  1027  	return nil // too far away
  1028  found:
  1029  	// At this point, r is the first value in a that we find by walking backwards.
  1030  	// if we return anything, r will be it.
  1031  	r := b
  1032  
  1033  	// Keep going, counting the other a's that we find. They must all dominate r.
  1034  	na := 0
  1035  	for d > 0 {
  1036  		for _, x := range a {
  1037  			if b == x.Block {
  1038  				na++
  1039  			}
  1040  		}
  1041  		if na == len(a) {
  1042  			// Found all of a in a backwards walk. We can return r.
  1043  			return r
  1044  		}
  1045  		if len(b.Preds) > 1 {
  1046  			return nil
  1047  		}
  1048  		b = b.Preds[0].b
  1049  		d--
  1050  
  1051  	}
  1052  	return nil // too far away
  1053  }
  1054  
  1055  // clobber invalidates values. Returns true.
  1056  // clobber is used by rewrite rules to:
  1057  //
  1058  //	A) make sure the values are really dead and never used again.
  1059  //	B) decrement use counts of the values' args.
  1060  func clobber(vv ...*Value) bool {
  1061  	for _, v := range vv {
  1062  		v.reset(OpInvalid)
  1063  		// Note: leave v.Block intact.  The Block field is used after clobber.
  1064  	}
  1065  	return true
  1066  }
  1067  
  1068  // resetCopy resets v to be a copy of arg.
  1069  // Always returns true.
  1070  func resetCopy(v *Value, arg *Value) bool {
  1071  	v.reset(OpCopy)
  1072  	v.AddArg(arg)
  1073  	return true
  1074  }
  1075  
  1076  // clobberIfDead resets v when use count is 1. Returns true.
  1077  // clobberIfDead is used by rewrite rules to decrement
  1078  // use counts of v's args when v is dead and never used.
  1079  func clobberIfDead(v *Value) bool {
  1080  	if v.Uses == 1 {
  1081  		v.reset(OpInvalid)
  1082  	}
  1083  	// Note: leave v.Block intact.  The Block field is used after clobberIfDead.
  1084  	return true
  1085  }
  1086  
  1087  // noteRule is an easy way to track if a rule is matched when writing
  1088  // new ones.  Make the rule of interest also conditional on
  1089  //
  1090  //	noteRule("note to self: rule of interest matched")
  1091  //
  1092  // and that message will print when the rule matches.
  1093  func noteRule(s string) bool {
  1094  	fmt.Println(s)
  1095  	return true
  1096  }
  1097  
  1098  // countRule increments Func.ruleMatches[key].
  1099  // If Func.ruleMatches is non-nil at the end
  1100  // of compilation, it will be printed to stdout.
  1101  // This is intended to make it easier to find which functions
  1102  // which contain lots of rules matches when developing new rules.
  1103  func countRule(v *Value, key string) bool {
  1104  	f := v.Block.Func
  1105  	if f.ruleMatches == nil {
  1106  		f.ruleMatches = make(map[string]int)
  1107  	}
  1108  	f.ruleMatches[key]++
  1109  	return true
  1110  }
  1111  
  1112  // warnRule generates compiler debug output with string s when
  1113  // v is not in autogenerated code, cond is true and the rule has fired.
  1114  func warnRule(cond bool, v *Value, s string) bool {
  1115  	if pos := v.Pos; pos.Line() > 1 && cond {
  1116  		v.Block.Func.Warnl(pos, s)
  1117  	}
  1118  	return true
  1119  }
  1120  
  1121  // for a pseudo-op like (LessThan x), extract x.
  1122  func flagArg(v *Value) *Value {
  1123  	if len(v.Args) != 1 || !v.Args[0].Type.IsFlags() {
  1124  		return nil
  1125  	}
  1126  	return v.Args[0]
  1127  }
  1128  
  1129  // amd64CapAVXShift caps an AMD64 AVX vector shift amount c so that over-shifts
  1130  // always result in 0.
  1131  //
  1132  // These instructions have room for an 8-bit immediate and any value larger than
  1133  // the element width will result in 0 or -1 (for an arithmetic right shift).
  1134  // Thus, we simply cap this at 255.
  1135  func amd64CapAVXShift(auxInt int64) uint8 {
  1136  	u := auxIntToUint64(auxInt)
  1137  	if u > 255 {
  1138  		return 255
  1139  	}
  1140  	return uint8(u)
  1141  }
  1142  
  1143  // arm64Negate finds the complement to an ARM64 condition code,
  1144  // for example !Equal -> NotEqual or !LessThan -> GreaterEqual
  1145  //
  1146  // For floating point, it's more subtle because NaN is unordered. We do
  1147  // !LessThanF -> NotLessThanF, the latter takes care of NaNs.
  1148  func arm64Negate(op Op) Op {
  1149  	switch op {
  1150  	case OpARM64LessThan:
  1151  		return OpARM64GreaterEqual
  1152  	case OpARM64LessThanU:
  1153  		return OpARM64GreaterEqualU
  1154  	case OpARM64GreaterThan:
  1155  		return OpARM64LessEqual
  1156  	case OpARM64GreaterThanU:
  1157  		return OpARM64LessEqualU
  1158  	case OpARM64LessEqual:
  1159  		return OpARM64GreaterThan
  1160  	case OpARM64LessEqualU:
  1161  		return OpARM64GreaterThanU
  1162  	case OpARM64GreaterEqual:
  1163  		return OpARM64LessThan
  1164  	case OpARM64GreaterEqualU:
  1165  		return OpARM64LessThanU
  1166  	case OpARM64Equal:
  1167  		return OpARM64NotEqual
  1168  	case OpARM64NotEqual:
  1169  		return OpARM64Equal
  1170  	case OpARM64LessThanF:
  1171  		return OpARM64NotLessThanF
  1172  	case OpARM64NotLessThanF:
  1173  		return OpARM64LessThanF
  1174  	case OpARM64LessEqualF:
  1175  		return OpARM64NotLessEqualF
  1176  	case OpARM64NotLessEqualF:
  1177  		return OpARM64LessEqualF
  1178  	case OpARM64GreaterThanF:
  1179  		return OpARM64NotGreaterThanF
  1180  	case OpARM64NotGreaterThanF:
  1181  		return OpARM64GreaterThanF
  1182  	case OpARM64GreaterEqualF:
  1183  		return OpARM64NotGreaterEqualF
  1184  	case OpARM64NotGreaterEqualF:
  1185  		return OpARM64GreaterEqualF
  1186  	default:
  1187  		panic("unreachable")
  1188  	}
  1189  }
  1190  
  1191  // arm64Invert evaluates (InvertFlags op), which
  1192  // is the same as altering the condition codes such
  1193  // that the same result would be produced if the arguments
  1194  // to the flag-generating instruction were reversed, e.g.
  1195  // (InvertFlags (CMP x y)) -> (CMP y x)
  1196  func arm64Invert(op Op) Op {
  1197  	switch op {
  1198  	case OpARM64LessThan:
  1199  		return OpARM64GreaterThan
  1200  	case OpARM64LessThanU:
  1201  		return OpARM64GreaterThanU
  1202  	case OpARM64GreaterThan:
  1203  		return OpARM64LessThan
  1204  	case OpARM64GreaterThanU:
  1205  		return OpARM64LessThanU
  1206  	case OpARM64LessEqual:
  1207  		return OpARM64GreaterEqual
  1208  	case OpARM64LessEqualU:
  1209  		return OpARM64GreaterEqualU
  1210  	case OpARM64GreaterEqual:
  1211  		return OpARM64LessEqual
  1212  	case OpARM64GreaterEqualU:
  1213  		return OpARM64LessEqualU
  1214  	case OpARM64Equal, OpARM64NotEqual:
  1215  		return op
  1216  	case OpARM64LessThanF:
  1217  		return OpARM64GreaterThanF
  1218  	case OpARM64GreaterThanF:
  1219  		return OpARM64LessThanF
  1220  	case OpARM64LessEqualF:
  1221  		return OpARM64GreaterEqualF
  1222  	case OpARM64GreaterEqualF:
  1223  		return OpARM64LessEqualF
  1224  	case OpARM64NotLessThanF:
  1225  		return OpARM64NotGreaterThanF
  1226  	case OpARM64NotGreaterThanF:
  1227  		return OpARM64NotLessThanF
  1228  	case OpARM64NotLessEqualF:
  1229  		return OpARM64NotGreaterEqualF
  1230  	case OpARM64NotGreaterEqualF:
  1231  		return OpARM64NotLessEqualF
  1232  	default:
  1233  		panic("unreachable")
  1234  	}
  1235  }
  1236  
  1237  // evaluate an ARM64 op against a flags value
  1238  // that is potentially constant; return 1 for true,
  1239  // -1 for false, and 0 for not constant.
  1240  func ccARM64Eval(op Op, flags *Value) int {
  1241  	fop := flags.Op
  1242  	if fop == OpARM64InvertFlags {
  1243  		return -ccARM64Eval(op, flags.Args[0])
  1244  	}
  1245  	if fop != OpARM64FlagConstant {
  1246  		return 0
  1247  	}
  1248  	fc := flagConstant(flags.AuxInt)
  1249  	b2i := func(b bool) int {
  1250  		if b {
  1251  			return 1
  1252  		}
  1253  		return -1
  1254  	}
  1255  	switch op {
  1256  	case OpARM64Equal:
  1257  		return b2i(fc.eq())
  1258  	case OpARM64NotEqual:
  1259  		return b2i(fc.ne())
  1260  	case OpARM64LessThan:
  1261  		return b2i(fc.lt())
  1262  	case OpARM64LessThanU:
  1263  		return b2i(fc.ult())
  1264  	case OpARM64GreaterThan:
  1265  		return b2i(fc.gt())
  1266  	case OpARM64GreaterThanU:
  1267  		return b2i(fc.ugt())
  1268  	case OpARM64LessEqual:
  1269  		return b2i(fc.le())
  1270  	case OpARM64LessEqualU:
  1271  		return b2i(fc.ule())
  1272  	case OpARM64GreaterEqual:
  1273  		return b2i(fc.ge())
  1274  	case OpARM64GreaterEqualU:
  1275  		return b2i(fc.uge())
  1276  	}
  1277  	return 0
  1278  }
  1279  
  1280  // logRule logs the use of the rule s. This will only be enabled if
  1281  // rewrite rules were generated with the -log option, see _gen/rulegen.go.
  1282  func logRule(s string) {
  1283  	if ruleFile == nil {
  1284  		// Open a log file to write log to. We open in append
  1285  		// mode because all.bash runs the compiler lots of times,
  1286  		// and we want the concatenation of all of those logs.
  1287  		// This means, of course, that users need to rm the old log
  1288  		// to get fresh data.
  1289  		// TODO: all.bash runs compilers in parallel. Need to synchronize logging somehow?
  1290  		w, err := os.OpenFile(filepath.Join(os.Getenv("GOROOT"), "src", "rulelog"),
  1291  			os.O_CREATE|os.O_WRONLY|os.O_APPEND, 0666)
  1292  		if err != nil {
  1293  			panic(err)
  1294  		}
  1295  		ruleFile = w
  1296  	}
  1297  	// Ignore errors in case of multiple processes fighting over the file.
  1298  	fmt.Fprintln(ruleFile, s)
  1299  }
  1300  
  1301  var ruleFile io.Writer
  1302  
  1303  func isConstZero(v *Value) bool {
  1304  	switch v.Op {
  1305  	case OpConstNil:
  1306  		return true
  1307  	case OpConst64, OpConst32, OpConst16, OpConst8, OpConstBool, OpConst32F, OpConst64F:
  1308  		return v.AuxInt == 0
  1309  	case OpStringMake, OpIMake, OpComplexMake:
  1310  		return isConstZero(v.Args[0]) && isConstZero(v.Args[1])
  1311  	case OpSliceMake:
  1312  		return isConstZero(v.Args[0]) && isConstZero(v.Args[1]) && isConstZero(v.Args[2])
  1313  	case OpStringPtr, OpStringLen, OpSlicePtr, OpSliceLen, OpSliceCap, OpITab, OpIData, OpComplexReal, OpComplexImag:
  1314  		return isConstZero(v.Args[0])
  1315  	}
  1316  	return false
  1317  }
  1318  
  1319  // reciprocalExact64 reports whether 1/c is exactly representable.
  1320  func reciprocalExact64(c float64) bool {
  1321  	b := math.Float64bits(c)
  1322  	man := b & (1<<52 - 1)
  1323  	if man != 0 {
  1324  		return false // not a power of 2, denormal, or NaN
  1325  	}
  1326  	exp := b >> 52 & (1<<11 - 1)
  1327  	// exponent bias is 0x3ff.  So taking the reciprocal of a number
  1328  	// changes the exponent to 0x7fe-exp.
  1329  	switch exp {
  1330  	case 0:
  1331  		return false // ±0
  1332  	case 0x7ff:
  1333  		return false // ±inf
  1334  	case 0x7fe:
  1335  		return false // exponent is not representable
  1336  	default:
  1337  		return true
  1338  	}
  1339  }
  1340  
  1341  // reciprocalExact32 reports whether 1/c is exactly representable.
  1342  func reciprocalExact32(c float32) bool {
  1343  	b := math.Float32bits(c)
  1344  	man := b & (1<<23 - 1)
  1345  	if man != 0 {
  1346  		return false // not a power of 2, denormal, or NaN
  1347  	}
  1348  	exp := b >> 23 & (1<<8 - 1)
  1349  	// exponent bias is 0x7f.  So taking the reciprocal of a number
  1350  	// changes the exponent to 0xfe-exp.
  1351  	switch exp {
  1352  	case 0:
  1353  		return false // ±0
  1354  	case 0xff:
  1355  		return false // ±inf
  1356  	case 0xfe:
  1357  		return false // exponent is not representable
  1358  	default:
  1359  		return true
  1360  	}
  1361  }
  1362  
  1363  // check if an immediate can be directly encoded into an ARM's instruction.
  1364  func isARMImmRot(v uint32) bool {
  1365  	for i := 0; i < 16; i++ {
  1366  		if v&^0xff == 0 {
  1367  			return true
  1368  		}
  1369  		v = v<<2 | v>>30
  1370  	}
  1371  
  1372  	return false
  1373  }
  1374  
  1375  // overlap reports whether the ranges given by the given offset and
  1376  // size pairs overlap.
  1377  func overlap(offset1, size1, offset2, size2 int64) bool {
  1378  	if offset1 >= offset2 && offset2+size2 > offset1 {
  1379  		return true
  1380  	}
  1381  	if offset2 >= offset1 && offset1+size1 > offset2 {
  1382  		return true
  1383  	}
  1384  	return false
  1385  }
  1386  
  1387  // ZeroUpper32Bits checks if value zeroes out upper 32-bit of 64-bit register.
  1388  // depth limits recursion depth. In AMD64.rules 3 is used as limit,
  1389  // because it catches same amount of cases as 4.
  1390  func ZeroUpper32Bits(x *Value) bool { return zeroUpperBits(x, 32, 3) }
  1391  
  1392  // ZeroUpper48Bits is similar to ZeroUpper32Bits, but for upper 48 bits.
  1393  func ZeroUpper48Bits(x *Value) bool { return zeroUpperBits(x, 48, 3) }
  1394  
  1395  // ZeroUpper56Bits is similar to ZeroUpper32Bits, but for upper 56 bits.
  1396  func ZeroUpper56Bits(x *Value) bool { return zeroUpperBits(x, 56, 3) }
  1397  
  1398  // zeroUpperBits reports whether the 64-bit register holding x provably has
  1399  // its upper `bits` bits zero, i.e. the value is below 2^(64-bits).
  1400  //
  1401  // Which ops guarantee this is declared per op in the _gen op definitions
  1402  // (the zeroUpperBits attribute); only the value-dependent cases live here.
  1403  func zeroUpperBits(x *Value, bits int64, depth int) bool {
  1404  	if x.Type.IsSigned() && 8*x.Type.Size() <= 64-bits {
  1405  		// A spill/restore sign-extends from the type's width (issue 68227).
  1406  		// A signed type no wider than the claimed value width may have its
  1407  		// sign bit set, so a restore can write ones into the upper bits.
  1408  		// Wider signed types are safe: their value is below the type's
  1409  		// sign bit, so a restore zero-extends.
  1410  		return false
  1411  	}
  1412  	if int64(opcodeTable[x.Op].zeroUpperBits) >= bits {
  1413  		return true
  1414  	}
  1415  	switch x.Op {
  1416  	case OpAMD64MOVQconst, OpAMD64MOVLconst:
  1417  		// A constant qualifies whenever its value fits the claimed width.
  1418  		// (MOVLconst always zeroes the upper 32 bits, so for bits==32 it
  1419  		// is already handled by its zeroUpperBits attribute.)
  1420  		return uint64(x.AuxInt)>>(64-bits) == 0
  1421  	case OpArg: // note: but not ArgIntReg
  1422  		// amd64 always loads args from the stack unsigned.
  1423  		// most other architectures load them sign/zero extended based on the type.
  1424  		return 8*x.Type.Size() == 64-bits && x.Block.Func.Config.arch == "amd64"
  1425  	case OpSelect0, OpSelect1:
  1426  		// A Select names one register result of a tuple-producing op, so
  1427  		// the question is what that op's write does. The op's attribute
  1428  		// covers every integer result; a Select of a non-covered result
  1429  		// (flags, memory) never appears as an operand of the rules that
  1430  		// ask about upper bits.
  1431  		return int64(opcodeTable[x.Args[0].Op].zeroUpperBits) >= bits
  1432  	case OpPhi:
  1433  		// Phis can use each-other as an arguments, instead of tracking visited values,
  1434  		// just limit recursion depth.
  1435  		if depth <= 0 {
  1436  			return false
  1437  		}
  1438  		for i := range x.Args {
  1439  			if !zeroUpperBits(x.Args[i], bits, depth-1) {
  1440  				return false
  1441  			}
  1442  		}
  1443  		return true
  1444  	}
  1445  	return false
  1446  }
  1447  
  1448  func isInlinableMemclr(c *Config, sz int64) bool {
  1449  	if sz < 0 {
  1450  		return false
  1451  	}
  1452  	// TODO: expand this check to allow other architectures
  1453  	// see CL 454255 and issue 56997
  1454  	switch c.arch {
  1455  	case "amd64", "arm64":
  1456  		return true
  1457  	case "ppc64le", "ppc64", "loong64":
  1458  		return sz < 512
  1459  	}
  1460  	return false
  1461  }
  1462  
  1463  // isInlinableMemmove reports whether the given arch performs a Move of the given size
  1464  // faster than memmove. It will only return true if replacing the memmove with a Move is
  1465  // safe, either because Move will do all of its loads before any of its stores, or
  1466  // because the arguments are known to be disjoint.
  1467  // This is used as a check for replacing memmove with Move ops.
  1468  func isInlinableMemmove(dst, src *Value, sz int64, c *Config) bool {
  1469  	// It is always safe to convert memmove into Move when its arguments are disjoint.
  1470  	// Move ops may or may not be faster for large sizes depending on how the platform
  1471  	// lowers them, so we only perform this optimization on platforms that we know to
  1472  	// have fast Move ops.
  1473  	switch c.arch {
  1474  	case "amd64":
  1475  		return sz <= 16 || (sz < 1024 && disjoint1(dst, sz, src, sz))
  1476  	case "arm64":
  1477  		return sz <= 64 || (sz <= 1024 && disjoint1(dst, sz, src, sz))
  1478  	case "loong64":
  1479  		return sz <= 16 || (sz <= 64 && disjoint1(dst, sz, src, sz))
  1480  	case "386":
  1481  		return sz <= 8
  1482  	case "s390x", "ppc64", "ppc64le":
  1483  		return sz <= 8 || disjoint1(dst, sz, src, sz)
  1484  	case "arm", "mips", "mips64", "mipsle", "mips64le":
  1485  		return sz <= 4
  1486  	}
  1487  	return false
  1488  }
  1489  func IsInlinableMemmove(dst, src *Value, sz int64, c *Config) bool {
  1490  	return isInlinableMemmove(dst, src, sz, c)
  1491  }
  1492  
  1493  // logLargeCopy logs the occurrence of a large copy.
  1494  // The best place to do this is in the rewrite rules where the size of the move is easy to find.
  1495  // "Large" is arbitrarily chosen to be 128 bytes; this may change.
  1496  func logLargeCopy(v *Value, s int64) bool {
  1497  	if s < 128 {
  1498  		return true
  1499  	}
  1500  	if logopt.Enabled() {
  1501  		logopt.LogOpt(v.Pos, "copy", "lower", v.Block.Func.Name, fmt.Sprintf("%d bytes", s))
  1502  	}
  1503  	return true
  1504  }
  1505  func LogLargeCopy(funcName string, pos src.XPos, s int64) {
  1506  	if s < 128 {
  1507  		return
  1508  	}
  1509  	if logopt.Enabled() {
  1510  		logopt.LogOpt(pos, "copy", "lower", funcName, fmt.Sprintf("%d bytes", s))
  1511  	}
  1512  }
  1513  
  1514  // hasSmallRotate reports whether the architecture has rotate instructions
  1515  // for sizes < 32-bit.  This is used to decide whether to promote some rotations.
  1516  func hasSmallRotate(c *Config) bool {
  1517  	switch c.arch {
  1518  	case "amd64", "386":
  1519  		return true
  1520  	default:
  1521  		return false
  1522  	}
  1523  }
  1524  
  1525  func supportsPPC64PCRel() bool {
  1526  	// PCRel is currently supported for >= power10, linux only
  1527  	// Internal and external linking supports this on ppc64le; internal linking on ppc64.
  1528  	return buildcfg.GOPPC64 >= 10 && buildcfg.GOOS == "linux"
  1529  }
  1530  
  1531  func newPPC64ShiftAuxInt(sh, mb, me, sz int64) int32 {
  1532  	if sh < 0 || sh >= sz {
  1533  		panic("PPC64 shift arg sh out of range")
  1534  	}
  1535  	if mb < 0 || mb >= sz {
  1536  		panic("PPC64 shift arg mb out of range")
  1537  	}
  1538  	if me < 0 || me >= sz {
  1539  		panic("PPC64 shift arg me out of range")
  1540  	}
  1541  	return int32(sh<<16 | mb<<8 | me)
  1542  }
  1543  
  1544  func GetPPC64Shiftsh(auxint int64) int64 {
  1545  	return int64(int8(auxint >> 16))
  1546  }
  1547  
  1548  func GetPPC64Shiftmb(auxint int64) int64 {
  1549  	return int64(int8(auxint >> 8))
  1550  }
  1551  
  1552  // Test if this value can encoded as a mask for a rlwinm like
  1553  // operation.  Masks can also extend from the msb and wrap to
  1554  // the lsb too.  That is, the valid masks are 32 bit strings
  1555  // of the form: 0..01..10..0 or 1..10..01..1 or 1...1
  1556  //
  1557  // Note: This ignores the upper 32 bits of the input. When a
  1558  // zero extended result is desired (e.g a 64 bit result), the
  1559  // user must verify the upper 32 bits are 0 and the mask is
  1560  // contiguous (that is, non-wrapping).
  1561  func isPPC64WordRotateMask(v64 int64) bool {
  1562  	// Isolate rightmost 1 (if none 0) and add.
  1563  	v := uint32(v64)
  1564  	vp := (v & -v) + v
  1565  	// Likewise, for the wrapping case.
  1566  	vn := ^v
  1567  	vpn := (vn & -vn) + vn
  1568  	return (v&vp == 0 || vn&vpn == 0) && v != 0
  1569  }
  1570  
  1571  // Test if this mask is a valid, contiguous bitmask which can be
  1572  // represented by a RLWNM mask and also clears the upper 32 bits
  1573  // of the register.
  1574  func isPPC64WordRotateMaskNonWrapping(v64 int64) bool {
  1575  	// Isolate rightmost 1 (if none 0) and add.
  1576  	v := uint32(v64)
  1577  	vp := (v & -v) + v
  1578  	return (v&vp == 0) && v != 0 && uint64(uint32(v64)) == uint64(v64)
  1579  }
  1580  
  1581  // Compress mask and shift into single value of the form
  1582  // me | mb<<8 | rotate<<16 | nbits<<24 where me and mb can
  1583  // be used to regenerate the input mask.
  1584  func encodePPC64RotateMask(rotate, mask, nbits int64) int64 {
  1585  	var mb, me, mbn, men int
  1586  
  1587  	// Determine boundaries and then decode them
  1588  	if mask == 0 || ^mask == 0 || rotate >= nbits {
  1589  		panic(fmt.Sprintf("invalid PPC64 rotate mask: %x %d %d", uint64(mask), rotate, nbits))
  1590  	} else if nbits == 32 {
  1591  		mb = bits.LeadingZeros32(uint32(mask))
  1592  		me = 32 - bits.TrailingZeros32(uint32(mask))
  1593  		mbn = bits.LeadingZeros32(^uint32(mask))
  1594  		men = 32 - bits.TrailingZeros32(^uint32(mask))
  1595  	} else {
  1596  		mb = bits.LeadingZeros64(uint64(mask))
  1597  		me = 64 - bits.TrailingZeros64(uint64(mask))
  1598  		mbn = bits.LeadingZeros64(^uint64(mask))
  1599  		men = 64 - bits.TrailingZeros64(^uint64(mask))
  1600  	}
  1601  	// Check for a wrapping mask (e.g bits at 0 and 63)
  1602  	if mb == 0 && me == int(nbits) {
  1603  		// swap the inverted values
  1604  		mb, me = men, mbn
  1605  	}
  1606  
  1607  	return int64(me) | int64(mb<<8) | rotate<<16 | nbits<<24
  1608  }
  1609  
  1610  // Merge (RLDICL [encoded] (SRDconst [s] x)) into (RLDICL [new_encoded] x)
  1611  // SRDconst on PPC64 is an extended mnemonic of RLDICL. If the input to an
  1612  // RLDICL is an SRDconst, and the RLDICL does not rotate its value, the two
  1613  // operations can be combined. This functions assumes the two opcodes can
  1614  // be merged, and returns an encoded rotate+mask value of the combined RLDICL.
  1615  func mergePPC64RLDICLandSRDconst(encoded, s int64) int64 {
  1616  	mb := s
  1617  	r := 64 - s
  1618  	// A larger mb is a smaller mask.
  1619  	if (encoded>>8)&0xFF < mb {
  1620  		encoded = (encoded &^ 0xFF00) | mb<<8
  1621  	}
  1622  	// The rotate is expected to be 0.
  1623  	if (encoded & 0xFF0000) != 0 {
  1624  		panic("non-zero rotate")
  1625  	}
  1626  	return encoded | r<<16
  1627  }
  1628  
  1629  // DecodePPC64RotateMask is the inverse operation of encodePPC64RotateMask.  The values returned as
  1630  // mb and me satisfy the POWER ISA definition of MASK(x,y) where MASK(mb,me) = mask.
  1631  func DecodePPC64RotateMask(sauxint int64) (rotate, mb, me int64, mask uint64) {
  1632  	auxint := uint64(sauxint)
  1633  	rotate = int64((auxint >> 16) & 0xFF)
  1634  	mb = int64((auxint >> 8) & 0xFF)
  1635  	me = int64((auxint >> 0) & 0xFF)
  1636  	nbits := int64((auxint >> 24) & 0xFF)
  1637  	mask = ((1 << uint(nbits-mb)) - 1) ^ ((1 << uint(nbits-me)) - 1)
  1638  	if mb > me {
  1639  		mask = ^mask
  1640  	}
  1641  	if nbits == 32 {
  1642  		mask = uint64(uint32(mask))
  1643  	}
  1644  
  1645  	// Fixup ME to match ISA definition.  The second argument to MASK(..,me)
  1646  	// is inclusive.
  1647  	me = (me - 1) & (nbits - 1)
  1648  	return
  1649  }
  1650  
  1651  // This verifies that the mask is a set of
  1652  // consecutive bits including the least
  1653  // significant bit.
  1654  func isPPC64ValidShiftMask(v int64) bool {
  1655  	if (v != 0) && ((v+1)&v) == 0 {
  1656  		return true
  1657  	}
  1658  	return false
  1659  }
  1660  
  1661  func getPPC64ShiftMaskLength(v int64) int64 {
  1662  	return int64(bits.Len64(uint64(v)))
  1663  }
  1664  
  1665  // Decompose a shift right into an equivalent rotate/mask,
  1666  // and return mask & m.
  1667  func mergePPC64RShiftMask(m, s, nbits int64) int64 {
  1668  	smask := uint64((1<<uint(nbits))-1) >> uint(s)
  1669  	return m & int64(smask)
  1670  }
  1671  
  1672  // Combine (ANDconst [m] (SRWconst [s])) into (RLWINM [y]) or return 0
  1673  func mergePPC64AndSrwi(m, s int64) int64 {
  1674  	mask := mergePPC64RShiftMask(m, s, 32)
  1675  	if !isPPC64WordRotateMask(mask) {
  1676  		return 0
  1677  	}
  1678  	return encodePPC64RotateMask((32-s)&31, mask, 32)
  1679  }
  1680  
  1681  // Combine (ANDconst [m] (SRDconst [s])) into (RLWINM [y]) or return 0
  1682  func mergePPC64AndSrdi(m, s int64) int64 {
  1683  	mask := mergePPC64RShiftMask(m, s, 64)
  1684  
  1685  	// Verify the rotate and mask result only uses the lower 32 bits.
  1686  	rv := bits.RotateLeft64(0xFFFFFFFF00000000, -int(s))
  1687  	if rv&uint64(mask) != 0 {
  1688  		return 0
  1689  	}
  1690  	if !isPPC64WordRotateMaskNonWrapping(mask) {
  1691  		return 0
  1692  	}
  1693  	return encodePPC64RotateMask((32-s)&31, mask, 32)
  1694  }
  1695  
  1696  // Combine (ANDconst [m] (SLDconst [s])) into (RLWINM [y]) or return 0
  1697  func mergePPC64AndSldi(m, s int64) int64 {
  1698  	mask := -1 << s & m
  1699  
  1700  	// Verify the rotate and mask result only uses the lower 32 bits.
  1701  	rv := bits.RotateLeft64(0xFFFFFFFF00000000, int(s))
  1702  	if rv&uint64(mask) != 0 {
  1703  		return 0
  1704  	}
  1705  	if !isPPC64WordRotateMaskNonWrapping(mask) {
  1706  		return 0
  1707  	}
  1708  	return encodePPC64RotateMask(s&31, mask, 32)
  1709  }
  1710  
  1711  // Test if a word shift right feeding into a CLRLSLDI can be merged into RLWINM.
  1712  // Return the encoded RLWINM constant, or 0 if they cannot be merged.
  1713  func mergePPC64ClrlsldiSrw(sld, srw int64) int64 {
  1714  	mask_1 := uint64(0xFFFFFFFF >> uint(srw))
  1715  	// for CLRLSLDI, it's more convenient to think of it as a mask left bits then rotate left.
  1716  	mask_2 := uint64(0xFFFFFFFFFFFFFFFF) >> uint(GetPPC64Shiftmb(sld))
  1717  
  1718  	// Rewrite mask to apply after the final left shift.
  1719  	mask_3 := (mask_1 & mask_2) << uint(GetPPC64Shiftsh(sld))
  1720  
  1721  	r_1 := 32 - srw
  1722  	r_2 := GetPPC64Shiftsh(sld)
  1723  	r_3 := (r_1 + r_2) & 31 // This can wrap.
  1724  
  1725  	if uint64(uint32(mask_3)) != mask_3 || mask_3 == 0 {
  1726  		return 0
  1727  	}
  1728  	return encodePPC64RotateMask(r_3, int64(mask_3), 32)
  1729  }
  1730  
  1731  // Test if a doubleword shift right feeding into a CLRLSLDI can be merged into RLWINM.
  1732  // Return the encoded RLWINM constant, or 0 if they cannot be merged.
  1733  func mergePPC64ClrlsldiSrd(sld, srd int64) int64 {
  1734  	mask_1 := uint64(0xFFFFFFFFFFFFFFFF) >> uint(srd)
  1735  	// for CLRLSLDI, it's more convenient to think of it as a mask left bits then rotate left.
  1736  	mask_2 := uint64(0xFFFFFFFFFFFFFFFF) >> uint(GetPPC64Shiftmb(sld))
  1737  
  1738  	// Rewrite mask to apply after the final left shift.
  1739  	mask_3 := (mask_1 & mask_2) << uint(GetPPC64Shiftsh(sld))
  1740  
  1741  	r_1 := 64 - srd
  1742  	r_2 := GetPPC64Shiftsh(sld)
  1743  	r_3 := (r_1 + r_2) & 63 // This can wrap.
  1744  
  1745  	if uint64(uint32(mask_3)) != mask_3 || mask_3 == 0 {
  1746  		return 0
  1747  	}
  1748  	// This combine only works when selecting and shifting the lower 32 bits.
  1749  	v1 := bits.RotateLeft64(0xFFFFFFFF00000000, int(r_3))
  1750  	if v1&mask_3 != 0 {
  1751  		return 0
  1752  	}
  1753  	return encodePPC64RotateMask(r_3&31, int64(mask_3), 32)
  1754  }
  1755  
  1756  // Test if a RLWINM feeding into a CLRLSLDI can be merged into RLWINM.  Return
  1757  // the encoded RLWINM constant, or 0 if they cannot be merged.
  1758  func mergePPC64ClrlsldiRlwinm(sld int32, rlw int64) int64 {
  1759  	r_1, _, _, mask_1 := DecodePPC64RotateMask(rlw)
  1760  	// for CLRLSLDI, it's more convenient to think of it as a mask left bits then rotate left.
  1761  	mask_2 := uint64(0xFFFFFFFFFFFFFFFF) >> uint(GetPPC64Shiftmb(int64(sld)))
  1762  
  1763  	// combine the masks, and adjust for the final left shift.
  1764  	mask_3 := (mask_1 & mask_2) << uint(GetPPC64Shiftsh(int64(sld)))
  1765  	r_2 := GetPPC64Shiftsh(int64(sld))
  1766  	r_3 := (r_1 + r_2) & 31 // This can wrap.
  1767  
  1768  	// Verify the result is still a valid bitmask of <= 32 bits.
  1769  	if !isPPC64WordRotateMask(int64(mask_3)) || uint64(uint32(mask_3)) != mask_3 {
  1770  		return 0
  1771  	}
  1772  	return encodePPC64RotateMask(r_3, int64(mask_3), 32)
  1773  }
  1774  
  1775  // Test if RLWINM feeding into an ANDconst can be merged. Return the encoded RLWINM constant,
  1776  // or 0 if they cannot be merged.
  1777  func mergePPC64AndRlwinm(mask uint32, rlw int64) int64 {
  1778  	r, _, _, mask_rlw := DecodePPC64RotateMask(rlw)
  1779  	mask_out := (mask_rlw & uint64(mask))
  1780  
  1781  	// Verify the result is still a valid bitmask of <= 32 bits.
  1782  	if !isPPC64WordRotateMask(int64(mask_out)) {
  1783  		return 0
  1784  	}
  1785  	return encodePPC64RotateMask(r, int64(mask_out), 32)
  1786  }
  1787  
  1788  // Test if RLWINM opcode rlw clears the upper 32 bits of the
  1789  // result. Return rlw if it does, 0 otherwise.
  1790  func mergePPC64MovwzregRlwinm(rlw int64) int64 {
  1791  	_, mb, me, _ := DecodePPC64RotateMask(rlw)
  1792  	if mb > me {
  1793  		return 0
  1794  	}
  1795  	return rlw
  1796  }
  1797  
  1798  // Test if AND feeding into an ANDconst can be merged. Return the encoded RLWINM constant,
  1799  // or 0 if they cannot be merged.
  1800  func mergePPC64RlwinmAnd(rlw int64, mask uint32) int64 {
  1801  	r, _, _, mask_rlw := DecodePPC64RotateMask(rlw)
  1802  
  1803  	// Rotate the input mask, combine with the rlwnm mask, and test if it is still a valid rlwinm mask.
  1804  	r_mask := bits.RotateLeft32(mask, int(r))
  1805  
  1806  	mask_out := (mask_rlw & uint64(r_mask))
  1807  
  1808  	// Verify the result is still a valid bitmask of <= 32 bits.
  1809  	if !isPPC64WordRotateMask(int64(mask_out)) {
  1810  		return 0
  1811  	}
  1812  	return encodePPC64RotateMask(r, int64(mask_out), 32)
  1813  }
  1814  
  1815  // Test if RLWINM feeding into SRDconst can be merged. Return the encoded RLIWNM constant,
  1816  // or 0 if they cannot be merged.
  1817  func mergePPC64SldiRlwinm(sldi, rlw int64) int64 {
  1818  	r_1, mb, me, mask_1 := DecodePPC64RotateMask(rlw)
  1819  	if mb > me || mb < sldi {
  1820  		// Wrapping masks cannot be merged as the upper 32 bits are effectively undefined in this case.
  1821  		// Likewise, if mb is less than the shift amount, it cannot be merged.
  1822  		return 0
  1823  	}
  1824  	// combine the masks, and adjust for the final left shift.
  1825  	mask_3 := mask_1 << sldi
  1826  	r_3 := (r_1 + sldi) & 31 // This can wrap.
  1827  
  1828  	// Verify the result is still a valid bitmask of <= 32 bits.
  1829  	if uint64(uint32(mask_3)) != mask_3 {
  1830  		return 0
  1831  	}
  1832  	return encodePPC64RotateMask(r_3, int64(mask_3), 32)
  1833  }
  1834  
  1835  // Compute the encoded RLWINM constant from combining (SLDconst [sld] (SRWconst [srw] x)),
  1836  // or return 0 if they cannot be combined.
  1837  func mergePPC64SldiSrw(sld, srw int64) int64 {
  1838  	if sld > srw || srw >= 32 {
  1839  		return 0
  1840  	}
  1841  	mask_r := uint32(0xFFFFFFFF) >> uint(srw)
  1842  	mask_l := uint32(0xFFFFFFFF) >> uint(sld)
  1843  	mask := (mask_r & mask_l) << uint(sld)
  1844  	return encodePPC64RotateMask((32-srw+sld)&31, int64(mask), 32)
  1845  }
  1846  
  1847  // Convert a PPC64 opcode from the Op to OpCC form. This converts (op x y)
  1848  // to (Select0 (opCC x y)) without having to explicitly fixup every user
  1849  // of op.
  1850  //
  1851  // E.g consider the case:
  1852  // a = (ADD x y)
  1853  // b = (CMPconst [0] a)
  1854  // c = (OR a z)
  1855  //
  1856  // A rule like (CMPconst [0] (ADD x y)) => (CMPconst [0] (Select0 (ADDCC x y)))
  1857  // would produce:
  1858  // a  = (ADD x y)
  1859  // a' = (ADDCC x y)
  1860  // a” = (Select0 a')
  1861  // b  = (CMPconst [0] a”)
  1862  // c  = (OR a z)
  1863  //
  1864  // which makes it impossible to rewrite the second user. Instead the result
  1865  // of this conversion is:
  1866  // a' = (ADDCC x y)
  1867  // a  = (Select0 a')
  1868  // b  = (CMPconst [0] a)
  1869  // c  = (OR a z)
  1870  //
  1871  // Which makes it trivial to rewrite b using a lowering rule.
  1872  func convertPPC64OpToOpCC(op *Value) *Value {
  1873  	ccOpMap := map[Op]Op{
  1874  		OpPPC64ADD:      OpPPC64ADDCC,
  1875  		OpPPC64ADDconst: OpPPC64ADDCCconst,
  1876  		OpPPC64AND:      OpPPC64ANDCC,
  1877  		OpPPC64ANDN:     OpPPC64ANDNCC,
  1878  		OpPPC64ANDconst: OpPPC64ANDCCconst,
  1879  		OpPPC64CNTLZD:   OpPPC64CNTLZDCC,
  1880  		OpPPC64MULHDU:   OpPPC64MULHDUCC,
  1881  		OpPPC64NEG:      OpPPC64NEGCC,
  1882  		OpPPC64NOR:      OpPPC64NORCC,
  1883  		OpPPC64OR:       OpPPC64ORCC,
  1884  		OpPPC64RLDICL:   OpPPC64RLDICLCC,
  1885  		OpPPC64SUB:      OpPPC64SUBCC,
  1886  		OpPPC64XOR:      OpPPC64XORCC,
  1887  	}
  1888  	b := op.Block
  1889  	opCC := b.NewValue0I(op.Pos, ccOpMap[op.Op], types.NewTuple(op.Type, types.TypeFlags), op.AuxInt)
  1890  	opCC.AddArgs(op.Args...)
  1891  	op.reset(OpSelect0)
  1892  	op.AddArgs(opCC)
  1893  	return op
  1894  }
  1895  
  1896  // Try converting a RLDICL to ANDCC. If successful, return the mask otherwise 0.
  1897  func convertPPC64RldiclAndccconst(sauxint int64) int64 {
  1898  	r, _, _, mask := DecodePPC64RotateMask(sauxint)
  1899  	if r != 0 || mask&0xFFFF != mask {
  1900  		return 0
  1901  	}
  1902  	return int64(mask)
  1903  }
  1904  
  1905  // Convenience function to rotate a 32 bit constant value by another constant.
  1906  func rotateLeft32(v, rotate int64) int64 {
  1907  	return int64(bits.RotateLeft32(uint32(v), int(rotate)))
  1908  }
  1909  
  1910  func rotateRight64(v, rotate int64) int64 {
  1911  	return int64(bits.RotateLeft64(uint64(v), int(-rotate)))
  1912  }
  1913  
  1914  // encodes the lsb and width for arm(64) bitfield ops into the expected auxInt format.
  1915  func armBFAuxInt(lsb, width int64) arm64BitField {
  1916  	if lsb < 0 || lsb > 63 {
  1917  		panic("ARM(64) bit field lsb constant out of range")
  1918  	}
  1919  	if width < 1 || lsb+width > 64 {
  1920  		panic("ARM(64) bit field width constant out of range")
  1921  	}
  1922  	return arm64BitField(width | lsb<<8)
  1923  }
  1924  
  1925  // returns the lsb part of the auxInt field of arm64 bitfield ops.
  1926  func (bfc arm64BitField) lsb() int64 {
  1927  	return int64(uint64(bfc) >> 8)
  1928  }
  1929  
  1930  // returns the width part of the auxInt field of arm64 bitfield ops.
  1931  func (bfc arm64BitField) width() int64 {
  1932  	return int64(bfc) & 0xff
  1933  }
  1934  
  1935  // checks if mask >> rshift applied at lsb is a valid arm64 bitfield op mask.
  1936  func isARM64BFMask(lsb, mask, rshift int64) bool {
  1937  	shiftedMask := int64(uint64(mask) >> uint64(rshift))
  1938  	return shiftedMask != 0 && isPowerOfTwo(shiftedMask+1) && nto(shiftedMask)+lsb < 64
  1939  }
  1940  
  1941  // returns the bitfield width of mask >> rshift for arm64 bitfield ops.
  1942  func arm64BFWidth(mask, rshift int64) int64 {
  1943  	shiftedMask := int64(uint64(mask) >> uint64(rshift))
  1944  	if shiftedMask == 0 {
  1945  		panic("ARM64 BF mask is zero")
  1946  	}
  1947  	return nto(shiftedMask)
  1948  }
  1949  
  1950  // encodes condition code and NZCV flags into result.
  1951  func arm64ConditionalParamsAuxInt(cond Op, nzcv uint8) arm64ConditionalParams {
  1952  	if cond < OpARM64Equal || cond > OpARM64GreaterEqualU {
  1953  		panic("Wrong conditional operation")
  1954  	}
  1955  	if nzcv&0x0f != nzcv {
  1956  		panic("Wrong value of NZCV flag")
  1957  	}
  1958  	return arm64ConditionalParams{cond, nzcv, 0, false}
  1959  }
  1960  
  1961  // encodes condition code, NZCV flags and constant value into auxint.
  1962  func arm64ConditionalParamsAuxIntWithValue(cond Op, nzcv uint8, value uint8) arm64ConditionalParams {
  1963  	if value&0x1f != value {
  1964  		panic("Wrong value of constant")
  1965  	}
  1966  	params := arm64ConditionalParamsAuxInt(cond, nzcv)
  1967  	params.constValue = value
  1968  	params.ind = true
  1969  	return params
  1970  }
  1971  
  1972  // extracts condition code from auxint.
  1973  func (condParams arm64ConditionalParams) Cond() Op {
  1974  	return condParams.cond
  1975  }
  1976  
  1977  // extracts NZCV flags from auxint.
  1978  func (condParams arm64ConditionalParams) Nzcv() int64 {
  1979  	return int64(condParams.nzcv)
  1980  }
  1981  
  1982  // extracts constant value from auxint if present.
  1983  func (condParams arm64ConditionalParams) ConstValue() (int64, bool) {
  1984  	return int64(condParams.constValue), condParams.ind
  1985  }
  1986  
  1987  // registerizable reports whether t is a primitive type that fits in
  1988  // a register. It assumes float64 values will always fit into registers
  1989  // even if that isn't strictly true.
  1990  func registerizable(b *Block, typ *types.Type) bool {
  1991  	if typ.IsPtrShaped() || typ.IsFloat() || typ.IsBoolean() {
  1992  		return true
  1993  	}
  1994  	if typ.IsInteger() {
  1995  		return typ.Size() <= b.Func.Config.RegSize
  1996  	}
  1997  	return false
  1998  }
  1999  
  2000  // needRaceCleanup reports whether this call to racefuncenter/exit isn't needed.
  2001  func needRaceCleanup(sym *AuxCall, v *Value) bool {
  2002  	f := v.Block.Func
  2003  	if !f.Config.Race {
  2004  		return false
  2005  	}
  2006  	if !isSameCall(sym, "runtime.racefuncenter") && !isSameCall(sym, "runtime.racefuncexit") {
  2007  		return false
  2008  	}
  2009  	for _, b := range f.Blocks {
  2010  		for _, v := range b.Values {
  2011  			switch v.Op {
  2012  			case OpStaticCall, OpStaticLECall:
  2013  				// Check for racefuncenter will encounter racefuncexit and vice versa.
  2014  				// Allow calls to panic*
  2015  				s := v.Aux.(*AuxCall).Fn.String()
  2016  				switch s {
  2017  				case "runtime.racefuncenter", "runtime.racefuncexit",
  2018  					"runtime.panicdivide", "runtime.panicwrap",
  2019  					"runtime.panicshift":
  2020  					continue
  2021  				}
  2022  				// If we encountered any call, we need to keep racefunc*,
  2023  				// for accurate stacktraces.
  2024  				return false
  2025  			case OpPanicBounds, OpPanicExtend:
  2026  				// Note: these are panic generators that are ok (like the static calls above).
  2027  			case OpClosureCall, OpInterCall, OpClosureLECall, OpInterLECall:
  2028  				// We must keep the race functions if there are any other call types.
  2029  				return false
  2030  			}
  2031  		}
  2032  	}
  2033  	if isSameCall(sym, "runtime.racefuncenter") {
  2034  		// TODO REGISTER ABI this needs to be cleaned up.
  2035  		// If we're removing racefuncenter, remove its argument as well.
  2036  		if v.Args[0].Op != OpStore {
  2037  			if v.Op == OpStaticLECall {
  2038  				// there is no store, yet.
  2039  				return true
  2040  			}
  2041  			return false
  2042  		}
  2043  		mem := v.Args[0].Args[2]
  2044  		v.Args[0].reset(OpCopy)
  2045  		v.Args[0].AddArg(mem)
  2046  	}
  2047  	return true
  2048  }
  2049  
  2050  // symIsRO reports whether sym is a read-only global.
  2051  func symIsRO(sym Sym) bool {
  2052  	lsym := sym.(*obj.LSym)
  2053  	return lsym.Type == objabi.SRODATA && len(lsym.R) == 0
  2054  }
  2055  
  2056  // symIsROZero reports whether sym is a read-only global whose data contains all zeros.
  2057  func symIsROZero(sym Sym) bool {
  2058  	lsym := sym.(*obj.LSym)
  2059  	if lsym.Type != objabi.SRODATA || len(lsym.R) != 0 {
  2060  		return false
  2061  	}
  2062  	for _, b := range lsym.P {
  2063  		if b != 0 {
  2064  			return false
  2065  		}
  2066  	}
  2067  	return true
  2068  }
  2069  
  2070  // isFixedLoad returns true if the load can be resolved to fixed address or constant,
  2071  // and can be rewritten by rewriteFixedLoad.
  2072  func isFixedLoad(v *Value, sym Sym, off int64) bool {
  2073  	lsym := sym.(*obj.LSym)
  2074  	if (v.Type.IsPtrShaped() || v.Type.IsUintptr()) && lsym.Type == objabi.SRODATA {
  2075  		for _, r := range lsym.R {
  2076  			if (r.Type == objabi.R_ADDR || r.Type == objabi.R_WEAKADDR) && int64(r.Off) == off && r.Add == 0 {
  2077  				return true
  2078  			}
  2079  		}
  2080  		return false
  2081  	}
  2082  
  2083  	if ti := lsym.TypeInfo(); ti != nil {
  2084  		// Type symbols do not contain information about their fields, unlike the cases above.
  2085  		// Hand-implement field accesses.
  2086  		// TODO: can this be replaced with reflectdata.writeType and just use the code above?
  2087  
  2088  		t := ti.Type.(*types.Type)
  2089  
  2090  		for _, f := range rttype.Type.Fields() {
  2091  			if f.Offset == off && copyCompatibleType(v.Type, f.Type) {
  2092  				switch f.Sym.Name {
  2093  				case "Size_", "PtrBytes", "Hash", "Kind_", "GCData", "TFlag":
  2094  					return true
  2095  				default:
  2096  					// fmt.Println("unknown field", f.Sym.Name)
  2097  					return false
  2098  				}
  2099  			}
  2100  		}
  2101  
  2102  		if t.IsPtr() && off == rttype.PtrType.OffsetOf("Elem") {
  2103  			return true
  2104  		}
  2105  
  2106  		return false
  2107  	}
  2108  
  2109  	return false
  2110  }
  2111  
  2112  // rewriteFixedLoad rewrites a load to a fixed address or constant, if isFixedLoad returns true.
  2113  func rewriteFixedLoad(v *Value, sym Sym, sb *Value, off int64) *Value {
  2114  	b := v.Block
  2115  	f := b.Func
  2116  
  2117  	lsym := sym.(*obj.LSym)
  2118  	if (v.Type.IsPtrShaped() || v.Type.IsUintptr()) && lsym.Type == objabi.SRODATA {
  2119  		for _, r := range lsym.R {
  2120  			if (r.Type == objabi.R_ADDR || r.Type == objabi.R_WEAKADDR) && int64(r.Off) == off && r.Add == 0 {
  2121  				if strings.HasPrefix(r.Sym.Name, "type:") {
  2122  					// In case we're loading a type out of a dictionary, we need to record
  2123  					// that the containing function might put that type in an interface.
  2124  					// That information is currently recorded in relocations in the dictionary,
  2125  					// but if we perform this load at compile time then the dictionary
  2126  					// might be dead.
  2127  					reflectdata.MarkTypeSymUsedInInterface(r.Sym, f.fe.Func().Linksym())
  2128  				} else if strings.HasPrefix(r.Sym.Name, "go:itab") {
  2129  					// Same, but if we're using an itab we need to record that the
  2130  					// itab._type might be put in an interface.
  2131  					reflectdata.MarkTypeSymUsedInInterface(r.Sym, f.fe.Func().Linksym())
  2132  				}
  2133  				v.reset(OpAddr)
  2134  				v.Aux = symToAux(r.Sym)
  2135  				v.AddArg(sb)
  2136  				return v
  2137  			}
  2138  		}
  2139  		base.Fatalf("fixedLoad data not known for %s:%d", sym, off)
  2140  	}
  2141  
  2142  	if ti := lsym.TypeInfo(); ti != nil {
  2143  		// Type symbols do not contain information about their fields, unlike the cases above.
  2144  		// Hand-implement field accesses.
  2145  		// TODO: can this be replaced with reflectdata.writeType and just use the code above?
  2146  
  2147  		t := ti.Type.(*types.Type)
  2148  
  2149  		ptrSizedOpConst := OpConst64
  2150  		if f.Config.PtrSize == 4 {
  2151  			ptrSizedOpConst = OpConst32
  2152  		}
  2153  
  2154  		for _, f := range rttype.Type.Fields() {
  2155  			if f.Offset == off && copyCompatibleType(v.Type, f.Type) {
  2156  				switch f.Sym.Name {
  2157  				case "Size_":
  2158  					v.reset(ptrSizedOpConst)
  2159  					v.AuxInt = t.Size()
  2160  					return v
  2161  				case "PtrBytes":
  2162  					v.reset(ptrSizedOpConst)
  2163  					v.AuxInt = types.PtrDataSize(t)
  2164  					return v
  2165  				case "Hash":
  2166  					v.reset(OpConst32)
  2167  					v.AuxInt = int64(int32(types.TypeHash(t)))
  2168  					return v
  2169  				case "TFlag":
  2170  					v.reset(OpConst8)
  2171  					v.AuxInt = int64(t.TFlag())
  2172  					return v
  2173  				case "Kind_":
  2174  					v.reset(OpConst8)
  2175  					v.AuxInt = int64(int8(reflectdata.ABIKindOfType(t)))
  2176  					return v
  2177  				case "GCData":
  2178  					gcdata, _ := reflectdata.GCSym(t, true)
  2179  					v.reset(OpAddr)
  2180  					v.Aux = symToAux(gcdata)
  2181  					v.AddArg(sb)
  2182  					return v
  2183  				default:
  2184  					base.Fatalf("unknown field %s for fixedLoad of %s at offset %d", f.Sym.Name, lsym.Name, off)
  2185  				}
  2186  			}
  2187  		}
  2188  
  2189  		if t.IsPtr() && off == rttype.PtrType.OffsetOf("Elem") {
  2190  			elemSym := reflectdata.TypeLinksym(t.Elem())
  2191  			reflectdata.MarkTypeSymUsedInInterface(elemSym, f.fe.Func().Linksym())
  2192  			v.reset(OpAddr)
  2193  			v.Aux = symToAux(elemSym)
  2194  			v.AddArg(sb)
  2195  			return v
  2196  		}
  2197  
  2198  		base.Fatalf("fixedLoad data not known for %s:%d", sym, off)
  2199  	}
  2200  
  2201  	base.Fatalf("fixedLoad data not known for %s:%d", sym, off)
  2202  	return nil
  2203  }
  2204  
  2205  // read8 reads one byte from the read-only global sym at offset off.
  2206  func read8(sym Sym, off int64) uint8 {
  2207  	lsym := sym.(*obj.LSym)
  2208  	if off >= int64(len(lsym.P)) || off < 0 {
  2209  		// Invalid index into the global sym.
  2210  		// This can happen in dead code, so we don't want to panic.
  2211  		// Just return any value, it will eventually get ignored.
  2212  		// See issue 29215.
  2213  		return 0
  2214  	}
  2215  	return lsym.P[off]
  2216  }
  2217  
  2218  // read16 reads two bytes from the read-only global sym at offset off.
  2219  func read16(sym Sym, off int64, byteorder binary.ByteOrder) uint16 {
  2220  	lsym := sym.(*obj.LSym)
  2221  	// lsym.P is written lazily.
  2222  	// Bytes requested after the end of lsym.P are 0.
  2223  	var src []byte
  2224  	if 0 <= off && off < int64(len(lsym.P)) {
  2225  		src = lsym.P[off:]
  2226  	}
  2227  	buf := make([]byte, 2)
  2228  	copy(buf, src)
  2229  	return byteorder.Uint16(buf)
  2230  }
  2231  
  2232  // read32 reads four bytes from the read-only global sym at offset off.
  2233  func read32(sym Sym, off int64, byteorder binary.ByteOrder) uint32 {
  2234  	lsym := sym.(*obj.LSym)
  2235  	var src []byte
  2236  	if 0 <= off && off < int64(len(lsym.P)) {
  2237  		src = lsym.P[off:]
  2238  	}
  2239  	buf := make([]byte, 4)
  2240  	copy(buf, src)
  2241  	return byteorder.Uint32(buf)
  2242  }
  2243  
  2244  // read64 reads eight bytes from the read-only global sym at offset off.
  2245  func read64(sym Sym, off int64, byteorder binary.ByteOrder) uint64 {
  2246  	lsym := sym.(*obj.LSym)
  2247  	var src []byte
  2248  	if 0 <= off && off < int64(len(lsym.P)) {
  2249  		src = lsym.P[off:]
  2250  	}
  2251  	buf := make([]byte, 8)
  2252  	copy(buf, src)
  2253  	return byteorder.Uint64(buf)
  2254  }
  2255  
  2256  // sequentialAddresses reports true if it can prove that x + n == y
  2257  func sequentialAddresses(x, y *Value, n int64) bool {
  2258  	if x == y && n == 0 {
  2259  		return true
  2260  	}
  2261  	if x.Op == Op386ADDL && y.Op == Op386LEAL1 && y.AuxInt == n && y.Aux == nil &&
  2262  		(x.Args[0] == y.Args[0] && x.Args[1] == y.Args[1] ||
  2263  			x.Args[0] == y.Args[1] && x.Args[1] == y.Args[0]) {
  2264  		return true
  2265  	}
  2266  	if x.Op == Op386LEAL1 && y.Op == Op386LEAL1 && y.AuxInt == x.AuxInt+n && x.Aux == y.Aux &&
  2267  		(x.Args[0] == y.Args[0] && x.Args[1] == y.Args[1] ||
  2268  			x.Args[0] == y.Args[1] && x.Args[1] == y.Args[0]) {
  2269  		return true
  2270  	}
  2271  	if x.Op == OpAMD64ADDQ && y.Op == OpAMD64LEAQ1 && y.AuxInt == n && y.Aux == nil &&
  2272  		(x.Args[0] == y.Args[0] && x.Args[1] == y.Args[1] ||
  2273  			x.Args[0] == y.Args[1] && x.Args[1] == y.Args[0]) {
  2274  		return true
  2275  	}
  2276  	if x.Op == OpAMD64LEAQ1 && y.Op == OpAMD64LEAQ1 && y.AuxInt == x.AuxInt+n && x.Aux == y.Aux &&
  2277  		(x.Args[0] == y.Args[0] && x.Args[1] == y.Args[1] ||
  2278  			x.Args[0] == y.Args[1] && x.Args[1] == y.Args[0]) {
  2279  		return true
  2280  	}
  2281  	return false
  2282  }
  2283  
  2284  // flagConstant represents the result of a compile-time comparison.
  2285  // The sense of these flags does not necessarily represent the hardware's notion
  2286  // of a flags register - these are just a compile-time construct.
  2287  // We happen to match the semantics to those of arm/arm64.
  2288  // Note that these semantics differ from x86: the carry flag has the opposite
  2289  // sense on a subtraction!
  2290  //
  2291  //	On amd64, C=1 represents a borrow, e.g. SBB on amd64 does x - y - C.
  2292  //	On arm64, C=0 represents a borrow, e.g. SBC on arm64 does x - y - ^C.
  2293  //	 (because it does x + ^y + C).
  2294  //
  2295  // See https://en.wikipedia.org/wiki/Carry_flag#Vs._borrow_flag
  2296  type flagConstant uint8
  2297  
  2298  // N reports whether the result of an operation is negative (high bit set).
  2299  func (fc flagConstant) N() bool {
  2300  	return fc&1 != 0
  2301  }
  2302  
  2303  // Z reports whether the result of an operation is 0.
  2304  func (fc flagConstant) Z() bool {
  2305  	return fc&2 != 0
  2306  }
  2307  
  2308  // C reports whether an unsigned add overflowed (carry), or an
  2309  // unsigned subtract did not underflow (borrow).
  2310  func (fc flagConstant) C() bool {
  2311  	return fc&4 != 0
  2312  }
  2313  
  2314  // V reports whether a signed operation overflowed or underflowed.
  2315  func (fc flagConstant) V() bool {
  2316  	return fc&8 != 0
  2317  }
  2318  
  2319  func (fc flagConstant) eq() bool {
  2320  	return fc.Z()
  2321  }
  2322  func (fc flagConstant) ne() bool {
  2323  	return !fc.Z()
  2324  }
  2325  func (fc flagConstant) lt() bool {
  2326  	return fc.N() != fc.V()
  2327  }
  2328  func (fc flagConstant) le() bool {
  2329  	return fc.Z() || fc.lt()
  2330  }
  2331  func (fc flagConstant) gt() bool {
  2332  	return !fc.Z() && fc.ge()
  2333  }
  2334  func (fc flagConstant) ge() bool {
  2335  	return fc.N() == fc.V()
  2336  }
  2337  func (fc flagConstant) ult() bool {
  2338  	return !fc.C()
  2339  }
  2340  func (fc flagConstant) ule() bool {
  2341  	return fc.Z() || fc.ult()
  2342  }
  2343  func (fc flagConstant) ugt() bool {
  2344  	return !fc.Z() && fc.uge()
  2345  }
  2346  func (fc flagConstant) uge() bool {
  2347  	return fc.C()
  2348  }
  2349  
  2350  func (fc flagConstant) ltNoov() bool {
  2351  	return fc.lt() && !fc.V()
  2352  }
  2353  func (fc flagConstant) leNoov() bool {
  2354  	return fc.le() && !fc.V()
  2355  }
  2356  func (fc flagConstant) gtNoov() bool {
  2357  	return fc.gt() && !fc.V()
  2358  }
  2359  func (fc flagConstant) geNoov() bool {
  2360  	return fc.ge() && !fc.V()
  2361  }
  2362  
  2363  func (fc flagConstant) String() string {
  2364  	return fmt.Sprintf("N=%v,Z=%v,C=%v,V=%v", fc.N(), fc.Z(), fc.C(), fc.V())
  2365  }
  2366  
  2367  type flagConstantBuilder struct {
  2368  	N bool
  2369  	Z bool
  2370  	C bool
  2371  	V bool
  2372  }
  2373  
  2374  func (fcs flagConstantBuilder) encode() flagConstant {
  2375  	var fc flagConstant
  2376  	if fcs.N {
  2377  		fc |= 1
  2378  	}
  2379  	if fcs.Z {
  2380  		fc |= 2
  2381  	}
  2382  	if fcs.C {
  2383  		fc |= 4
  2384  	}
  2385  	if fcs.V {
  2386  		fc |= 8
  2387  	}
  2388  	return fc
  2389  }
  2390  
  2391  // Note: addFlags(x,y) != subFlags(x,-y) in some situations:
  2392  //  - the results of the C flag are different
  2393  //  - the results of the V flag when y==minint are different
  2394  
  2395  // addFlags64 returns the flags that would be set from computing x+y.
  2396  func addFlags64(x, y int64) flagConstant {
  2397  	var fcb flagConstantBuilder
  2398  	fcb.Z = x+y == 0
  2399  	fcb.N = x+y < 0
  2400  	fcb.C = uint64(x+y) < uint64(x)
  2401  	fcb.V = x >= 0 && y >= 0 && x+y < 0 || x < 0 && y < 0 && x+y >= 0
  2402  	return fcb.encode()
  2403  }
  2404  
  2405  // subFlags64 returns the flags that would be set from computing x-y.
  2406  func subFlags64(x, y int64) flagConstant {
  2407  	var fcb flagConstantBuilder
  2408  	fcb.Z = x-y == 0
  2409  	fcb.N = x-y < 0
  2410  	fcb.C = uint64(y) <= uint64(x) // This code follows the arm carry flag model.
  2411  	fcb.V = x >= 0 && y < 0 && x-y < 0 || x < 0 && y >= 0 && x-y >= 0
  2412  	return fcb.encode()
  2413  }
  2414  
  2415  // addFlags32 returns the flags that would be set from computing x+y.
  2416  func addFlags32(x, y int32) flagConstant {
  2417  	var fcb flagConstantBuilder
  2418  	fcb.Z = x+y == 0
  2419  	fcb.N = x+y < 0
  2420  	fcb.C = uint32(x+y) < uint32(x)
  2421  	fcb.V = x >= 0 && y >= 0 && x+y < 0 || x < 0 && y < 0 && x+y >= 0
  2422  	return fcb.encode()
  2423  }
  2424  
  2425  // subFlags32 returns the flags that would be set from computing x-y.
  2426  func subFlags32(x, y int32) flagConstant {
  2427  	var fcb flagConstantBuilder
  2428  	fcb.Z = x-y == 0
  2429  	fcb.N = x-y < 0
  2430  	fcb.C = uint32(y) <= uint32(x) // This code follows the arm carry flag model.
  2431  	fcb.V = x >= 0 && y < 0 && x-y < 0 || x < 0 && y >= 0 && x-y >= 0
  2432  	return fcb.encode()
  2433  }
  2434  
  2435  // logicFlags64 returns flags set to the sign/zeroness of x.
  2436  // C and V are set to false.
  2437  func logicFlags64(x int64) flagConstant {
  2438  	var fcb flagConstantBuilder
  2439  	fcb.Z = x == 0
  2440  	fcb.N = x < 0
  2441  	return fcb.encode()
  2442  }
  2443  
  2444  // logicFlags32 returns flags set to the sign/zeroness of x.
  2445  // C and V are set to false.
  2446  func logicFlags32(x int32) flagConstant {
  2447  	var fcb flagConstantBuilder
  2448  	fcb.Z = x == 0
  2449  	fcb.N = x < 0
  2450  	return fcb.encode()
  2451  }
  2452  
  2453  func makeJumpTableSym(b *Block) *obj.LSym {
  2454  	s := base.Ctxt.Lookup(fmt.Sprintf("%s.jump%d", b.Func.fe.Func().LSym.Name, b.ID))
  2455  	// The jump table symbol is accessed only from the function symbol.
  2456  	s.Set(obj.AttrStatic, true)
  2457  	return s
  2458  }
  2459  
  2460  // canRotate reports whether the architecture supports
  2461  // rotates of integer registers with the given number of bits.
  2462  func canRotate(c *Config, bits int64) bool {
  2463  	if bits > c.PtrSize*8 {
  2464  		// Don't rewrite to rotates bigger than the machine word.
  2465  		return false
  2466  	}
  2467  	switch c.arch {
  2468  	case "386", "amd64", "arm64", "loong64", "riscv64":
  2469  		return true
  2470  	case "arm", "s390x", "ppc64", "ppc64le", "wasm":
  2471  		return bits >= 32
  2472  	default:
  2473  		return false
  2474  	}
  2475  }
  2476  
  2477  // isARM64bitcon reports whether a constant can be encoded into a logical instruction.
  2478  func isARM64bitcon(x uint64) bool {
  2479  	if x == 1<<64-1 || x == 0 {
  2480  		return false
  2481  	}
  2482  	// determine the period and sign-extend a unit to 64 bits
  2483  	switch {
  2484  	case x != x>>32|x<<32:
  2485  		// period is 64
  2486  		// nothing to do
  2487  	case x != x>>16|x<<48:
  2488  		// period is 32
  2489  		x = uint64(int64(int32(x)))
  2490  	case x != x>>8|x<<56:
  2491  		// period is 16
  2492  		x = uint64(int64(int16(x)))
  2493  	case x != x>>4|x<<60:
  2494  		// period is 8
  2495  		x = uint64(int64(int8(x)))
  2496  	default:
  2497  		// period is 4 or 2, always true
  2498  		// 0001, 0010, 0100, 1000 -- 0001 rotate
  2499  		// 0011, 0110, 1100, 1001 -- 0011 rotate
  2500  		// 0111, 1011, 1101, 1110 -- 0111 rotate
  2501  		// 0101, 1010             -- 01   rotate, repeat
  2502  		return true
  2503  	}
  2504  	return sequenceOfOnes(x) || sequenceOfOnes(^x)
  2505  }
  2506  
  2507  // sequenceOfOnes tests whether a constant is a sequence of ones in binary, with leading and trailing zeros.
  2508  func sequenceOfOnes(x uint64) bool {
  2509  	y := x & -x // lowest set bit of x. x is good iff x+y is a power of 2
  2510  	y += x
  2511  	return (y-1)&y == 0
  2512  }
  2513  
  2514  // isARM64addcon reports whether x can be encoded as the immediate value in an ADD or SUB instruction.
  2515  func isARM64addcon(v int64) bool {
  2516  	/* uimm12 or uimm24? */
  2517  	if v < 0 {
  2518  		return false
  2519  	}
  2520  	if (v & 0xFFF) == 0 {
  2521  		v >>= 12
  2522  	}
  2523  	return v <= 0xFFF
  2524  }
  2525  
  2526  // setPos sets the position of v to pos, then returns true.
  2527  // Useful for setting the result of a rewrite's position to
  2528  // something other than the default.
  2529  func setPos(v *Value, pos src.XPos) bool {
  2530  	v.Pos = pos
  2531  	return true
  2532  }
  2533  
  2534  // isNonNegative reports whether v is known to be greater or equal to zero.
  2535  // Note that this is pretty simplistic. The prove pass generates more detailed
  2536  // nonnegative information about values.
  2537  func isNonNegative(v *Value) bool {
  2538  	if !v.Type.IsInteger() {
  2539  		v.Fatalf("isNonNegative bad type: %v", v.Type)
  2540  	}
  2541  	// TODO: return true if !v.Type.IsSigned()
  2542  	// SSA isn't type-safe enough to do that now (issue 37753).
  2543  	// The checks below depend only on the pattern of bits.
  2544  
  2545  	switch v.Op {
  2546  	case OpConst64:
  2547  		return v.AuxInt >= 0
  2548  
  2549  	case OpConst32:
  2550  		return int32(v.AuxInt) >= 0
  2551  
  2552  	case OpConst16:
  2553  		return int16(v.AuxInt) >= 0
  2554  
  2555  	case OpConst8:
  2556  		return int8(v.AuxInt) >= 0
  2557  
  2558  	case OpStringLen, OpSliceLen, OpSliceCap,
  2559  		OpZeroExt8to64, OpZeroExt16to64, OpZeroExt32to64,
  2560  		OpZeroExt8to32, OpZeroExt16to32, OpZeroExt8to16,
  2561  		OpCtz64, OpCtz32, OpCtz16, OpCtz8,
  2562  		OpCtz64NonZero, OpCtz32NonZero, OpCtz16NonZero, OpCtz8NonZero,
  2563  		OpBitLen64, OpBitLen32, OpBitLen16, OpBitLen8:
  2564  		return true
  2565  
  2566  	case OpRsh64Ux64, OpRsh32Ux64:
  2567  		by := v.Args[1]
  2568  		return by.Op == OpConst64 && by.AuxInt > 0
  2569  
  2570  	case OpRsh64x64, OpRsh32x64, OpRsh8x64, OpRsh16x64, OpRsh32x32, OpRsh64x32,
  2571  		OpSignExt32to64, OpSignExt16to64, OpSignExt8to64, OpSignExt16to32, OpSignExt8to32:
  2572  		return isNonNegative(v.Args[0])
  2573  
  2574  	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
  2575  		return isNonNegative(v.Args[0]) || isNonNegative(v.Args[1])
  2576  
  2577  	case OpMod64, OpMod32, OpMod16, OpMod8,
  2578  		OpDiv64, OpDiv32, OpDiv16, OpDiv8,
  2579  		OpOr64, OpOr32, OpOr16, OpOr8,
  2580  		OpXor64, OpXor32, OpXor16, OpXor8:
  2581  		return isNonNegative(v.Args[0]) && isNonNegative(v.Args[1])
  2582  
  2583  		// We could handle OpPhi here, but the improvements from doing
  2584  		// so are very minor, and it is neither simple nor cheap.
  2585  	}
  2586  	return false
  2587  }
  2588  
  2589  func rewriteStructLoad(v *Value) *Value {
  2590  	b := v.Block
  2591  	ptr := v.Args[0]
  2592  	mem := v.Args[1]
  2593  
  2594  	t := v.Type
  2595  	args := make([]*Value, t.NumFields())
  2596  	for i := range args {
  2597  		ft := t.FieldType(i)
  2598  		addr := b.NewValue1I(v.Pos, OpOffPtr, ft.PtrTo(), t.FieldOff(i), ptr)
  2599  		args[i] = b.NewValue2(v.Pos, OpLoad, ft, addr, mem)
  2600  	}
  2601  
  2602  	v.reset(OpStructMake)
  2603  	v.AddArgs(args...)
  2604  	return v
  2605  }
  2606  
  2607  func rewriteStructStore(v *Value) *Value {
  2608  	b := v.Block
  2609  	dst := v.Args[0]
  2610  	x := v.Args[1]
  2611  	if x.Op != OpStructMake {
  2612  		base.Fatalf("invalid struct store: %v", x)
  2613  	}
  2614  	mem := v.Args[2]
  2615  
  2616  	t := x.Type
  2617  	for i, arg := range x.Args {
  2618  		ft := t.FieldType(i)
  2619  
  2620  		addr := b.NewValue1I(v.Pos, OpOffPtr, ft.PtrTo(), t.FieldOff(i), dst)
  2621  		mem = b.NewValue3A(v.Pos, OpStore, types.TypeMem, typeToAux(ft), addr, arg, mem)
  2622  	}
  2623  
  2624  	return mem
  2625  }
  2626  
  2627  // isDirectAndComparableType reports whether v represents a type
  2628  // (a *runtime._type) whose value is stored directly in an
  2629  // interface (i.e., is pointer or pointer-like) and is comparable.
  2630  func isDirectAndComparableType(v *Value) bool {
  2631  	return isDirectAndComparableType1(v)
  2632  }
  2633  
  2634  // v is a type
  2635  func isDirectAndComparableType1(v *Value) bool {
  2636  	switch v.Op {
  2637  	case OpITab:
  2638  		return isDirectAndComparableType2(v.Args[0])
  2639  	case OpAddr:
  2640  		lsym := v.Aux.(*obj.LSym)
  2641  		if ti := lsym.TypeInfo(); ti != nil {
  2642  			t := ti.Type.(*types.Type)
  2643  			return types.IsDirectIface(t) && types.IsComparable(t)
  2644  		}
  2645  	}
  2646  	return false
  2647  }
  2648  
  2649  // v is an empty interface
  2650  func isDirectAndComparableType2(v *Value) bool {
  2651  	switch v.Op {
  2652  	case OpIMake:
  2653  		return isDirectAndComparableType1(v.Args[0])
  2654  	}
  2655  	return false
  2656  }
  2657  
  2658  // isDirectAndComparableIface reports whether v represents an itab
  2659  // (a *runtime._itab) for a type whose value is stored directly
  2660  // in an interface (i.e., is pointer or pointer-like) and is comparable.
  2661  func isDirectAndComparableIface(v *Value) bool {
  2662  	return isDirectAndComparableIface1(v, 9)
  2663  }
  2664  
  2665  // v is an itab
  2666  func isDirectAndComparableIface1(v *Value, depth int) bool {
  2667  	if depth == 0 {
  2668  		return false
  2669  	}
  2670  	switch v.Op {
  2671  	case OpITab:
  2672  		return isDirectAndComparableIface2(v.Args[0], depth-1)
  2673  	case OpAddr:
  2674  		lsym := v.Aux.(*obj.LSym)
  2675  		if ii := lsym.ItabInfo(); ii != nil {
  2676  			t := ii.Type.(*types.Type)
  2677  			return types.IsDirectIface(t) && types.IsComparable(t)
  2678  		}
  2679  	case OpConstNil:
  2680  		// We can treat this as direct, because if the itab is
  2681  		// nil, the data field must be nil also.
  2682  		return true
  2683  	}
  2684  	return false
  2685  }
  2686  
  2687  // v is an interface
  2688  func isDirectAndComparableIface2(v *Value, depth int) bool {
  2689  	if depth == 0 {
  2690  		return false
  2691  	}
  2692  	switch v.Op {
  2693  	case OpIMake:
  2694  		return isDirectAndComparableIface1(v.Args[0], depth-1)
  2695  	case OpPhi:
  2696  		for _, a := range v.Args {
  2697  			if !isDirectAndComparableIface2(a, depth-1) {
  2698  				return false
  2699  			}
  2700  		}
  2701  		return true
  2702  	}
  2703  	return false
  2704  }
  2705  
  2706  func bitsAdd64(x, y, carry int64) (r struct{ sum, carry int64 }) {
  2707  	s, c := bits.Add64(uint64(x), uint64(y), uint64(carry))
  2708  	r.sum, r.carry = int64(s), int64(c)
  2709  	return
  2710  }
  2711  
  2712  func bitsSub64(x, y, borrow int64) (r struct{ diff, borrow int64 }) {
  2713  	d, b := bits.Sub64(uint64(x), uint64(y), uint64(borrow))
  2714  	r.diff, r.borrow = int64(d), int64(b)
  2715  	return
  2716  }
  2717  
  2718  func bitsDiv128u(hi, lo, y int64) (r struct{ quo, rem int64 }) {
  2719  	q, rem := bits.Div64(uint64(hi), uint64(lo), uint64(y))
  2720  	r.quo, r.rem = int64(q), int64(rem)
  2721  	return
  2722  }
  2723  
  2724  func bitsMulU64(x, y int64) (r struct{ hi, lo int64 }) {
  2725  	hi, lo := bits.Mul64(uint64(x), uint64(y))
  2726  	r.hi, r.lo = int64(hi), int64(lo)
  2727  	return
  2728  }
  2729  func bitsMulU32(x, y int32) (r struct{ hi, lo int32 }) {
  2730  	hi, lo := bits.Mul32(uint32(x), uint32(y))
  2731  	r.hi, r.lo = int32(hi), int32(lo)
  2732  	return
  2733  }
  2734  
  2735  // flagify rewrites v which is (X ...) to (Select0 (Xflags ...)).
  2736  func flagify(v *Value) bool {
  2737  	var flagVersion Op
  2738  	switch v.Op {
  2739  	case OpAMD64ADDQconst:
  2740  		flagVersion = OpAMD64ADDQconstflags
  2741  	case OpAMD64ADDLconst:
  2742  		flagVersion = OpAMD64ADDLconstflags
  2743  	default:
  2744  		base.Fatalf("can't flagify op %s", v.Op)
  2745  	}
  2746  	inner := v.copyInto(v.Block)
  2747  	inner.Op = flagVersion
  2748  	inner.Type = types.NewTuple(v.Type, types.TypeFlags)
  2749  	v.reset(OpSelect0)
  2750  	v.AddArg(inner)
  2751  	return true
  2752  }
  2753  
  2754  // PanicBoundsC contains a constant for a bounds failure.
  2755  type PanicBoundsC struct {
  2756  	C int64
  2757  }
  2758  
  2759  // PanicBoundsCC contains 2 constants for a bounds failure.
  2760  type PanicBoundsCC struct {
  2761  	Cx int64
  2762  	Cy int64
  2763  }
  2764  
  2765  func (p PanicBoundsC) CanBeAnSSAAux() {
  2766  }
  2767  func (p PanicBoundsCC) CanBeAnSSAAux() {
  2768  }
  2769  
  2770  func auxToPanicBoundsC(i Aux) PanicBoundsC {
  2771  	return i.(PanicBoundsC)
  2772  }
  2773  func auxToPanicBoundsCC(i Aux) PanicBoundsCC {
  2774  	return i.(PanicBoundsCC)
  2775  }
  2776  func panicBoundsCToAux(p PanicBoundsC) Aux {
  2777  	return p
  2778  }
  2779  func panicBoundsCCToAux(p PanicBoundsCC) Aux {
  2780  	return p
  2781  }
  2782  
  2783  func isDictArgSym(sym Sym) bool {
  2784  	return sym.(*ir.Name).Sym().Name == typecheck.LocalDictName
  2785  }
  2786  
  2787  // When v is (IMake typ (StructMake ...)), convert to
  2788  // (IMake typ arg) where arg is the pointer-y argument to
  2789  // the StructMake (there must be exactly one).
  2790  func imakeOfStructMake(v *Value) *Value {
  2791  	var arg *Value
  2792  	for _, a := range v.Args[1].Args {
  2793  		if a.Type.Size() > 0 {
  2794  			arg = a
  2795  			break
  2796  		}
  2797  	}
  2798  	return v.Block.NewValue2(v.Pos, OpIMake, v.Type, v.Args[0], arg)
  2799  }
  2800  
  2801  // bool2int converts bool to int: true to 1, false to 0
  2802  func bool2int(x bool) int {
  2803  	var b int
  2804  	if x {
  2805  		b = 1
  2806  	}
  2807  	return b
  2808  }
  2809  
  2810  // rewriteCondSelectIntoMath reports whether x OP (y * constant) should be used instead of a CondSelect.
  2811  // x arbitrary, y in [0,1]
  2812  func rewriteCondSelectIntoMath(config *Config, op Op, constant int64) bool {
  2813  	switch config.arch {
  2814  	case "amd64":
  2815  		// constant=1 becomes zext, add 2/4/8 becomes lea, rest becomes shl.
  2816  		// shl has asymmetric latency (1:3 vs 2:2) but performs better in accumulation chains.
  2817  		return isPowerOfTwo(uint64(constant))
  2818  	case "arm64":
  2819  		switch op {
  2820  		case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
  2821  			if constant == 1 {
  2822  				return false // better done as CSINC
  2823  			}
  2824  			fallthrough
  2825  		case OpSub64, OpSub32, OpSub16, OpSub8,
  2826  			OpAnd64, OpAnd32, OpAnd16, OpAnd8,
  2827  			OpOr64, OpOr32, OpOr16, OpOr8,
  2828  			OpXor64, OpXor32, OpXor16, OpXor8:
  2829  			// Implemented using an inline LSL
  2830  			return isPowerOfTwo(uint64(constant))
  2831  		default:
  2832  			if constant == 1 {
  2833  				return true
  2834  			}
  2835  		}
  2836  	default:
  2837  		// TODO: fine tune for other architectures.
  2838  		return constant == 1
  2839  	}
  2840  	return false
  2841  }
  2842  
  2843  func addToSub(op Op) Op {
  2844  	switch op {
  2845  	case OpAdd64:
  2846  		return OpSub64
  2847  	case OpAdd32:
  2848  		return OpSub32
  2849  	case OpAdd16:
  2850  		return OpSub16
  2851  	case OpAdd8:
  2852  		return OpSub8
  2853  	default:
  2854  		panic(fmt.Sprintf("unexpected op %v", op))
  2855  	}
  2856  }
  2857  
  2858  func modularMultiplicativeInverse(x uint64) (y uint64) {
  2859  	if x%2 != 1 {
  2860  		panic("even numbers in a power-of-two modulus do not have a multiplicative inverse")
  2861  	}
  2862  	// we start with 3 bits of precision because each odd number is its own multiplicative inverse mod 8
  2863  	y = x // 3 bits
  2864  
  2865  	// now use the Newton-Raphson method to double the number of correct bits in each iteration.
  2866  	y *= 2 - x*y // 6 bits
  2867  	y *= 2 - x*y // 12 bits
  2868  	y *= 2 - x*y // 24 bits
  2869  	y *= 2 - x*y // 48 bits
  2870  	y *= 2 - x*y // 96 bits; good enough
  2871  	return
  2872  }
  2873  
  2874  func invertibleBool(op Op) bool {
  2875  	switch op {
  2876  	case OpLess64, OpLess32, OpLess16, OpLess8,
  2877  		OpLeq64, OpLeq32, OpLeq16, OpLeq8,
  2878  		OpLess64U, OpLess32U, OpLess16U, OpLess8U,
  2879  		OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U,
  2880  		OpEq64, OpEq32, OpEq16, OpEq8,
  2881  		OpNeq64, OpNeq32, OpNeq16, OpNeq8,
  2882  		OpNot:
  2883  		return true
  2884  	default:
  2885  		return false
  2886  	}
  2887  }
  2888  

View as plain text