deadstore.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 ssacompile
     6  
     7  import (
     8  	"cmd/compile/internal/ir"
     9  	"cmd/compile/internal/ssa"
    10  	"cmd/compile/internal/ssa/ssaop"
    11  	"cmd/compile/internal/types"
    12  	"cmd/internal/obj"
    13  )
    14  
    15  // maxShadowRanges bounds the number of disjoint byte intervals
    16  // we track per pointer to avoid quadratic behaviour.
    17  const maxShadowRanges = 64
    18  
    19  // dse does dead-store elimination on the Function.
    20  // Dead stores are those which are unconditionally followed by
    21  // another store to the same location, with no intervening load.
    22  // This implementation only works within a basic block. TODO: use something more global.
    23  func dse(f *ssa.Func) {
    24  	var stores []*ssa.Value
    25  	loadUse := f.NewSparseSet(f.NumValues())
    26  	defer f.RetSparseSet(loadUse)
    27  	storeUse := f.NewSparseSet(f.NumValues())
    28  	defer f.RetSparseSet(storeUse)
    29  	shadowed := f.NewSparseMap(f.NumValues())
    30  	defer f.RetSparseMap(shadowed)
    31  	// localAddrs maps from a local variable (the Aux field of a LocalAddr value) to an instance of a LocalAddr value for that variable in the current block.
    32  	localAddrs := map[any]*ssa.Value{}
    33  
    34  	// shadowedRanges stores the actual range data. The 'shadowed' sparseMap stores a 1-based index into this slice.
    35  	var shadowedRanges []*shadowRanges
    36  
    37  	for _, b := range f.Blocks {
    38  		// Find all the stores in this block. Categorize their uses:
    39  		//  loadUse contains stores which are used by a subsequent load.
    40  		//  storeUse contains stores which are used by a subsequent store.
    41  		loadUse.Clear()
    42  		storeUse.Clear()
    43  		clear(localAddrs)
    44  		stores = stores[:0]
    45  		for _, v := range b.Values {
    46  			if v.Op == ssaop.OpPhi {
    47  				// Ignore phis - they will always be first and can't be eliminated
    48  				continue
    49  			}
    50  			if v.Type.IsMemory() {
    51  				stores = append(stores, v)
    52  				for _, a := range v.Args {
    53  					if a.Block == b && a.Type.IsMemory() {
    54  						storeUse.Add(a.ID)
    55  						switch v.Op {
    56  						case ssaop.OpStore, ssaop.OpZero, ssaop.OpVarDef:
    57  							// These ops never read from their memory input.
    58  						case ssaop.OpMove:
    59  							// This op reads from its memory argument, but
    60  							// we can treat it as not doing so if we know
    61  							// the read is from read-only memory.
    62  							if v.Args[1].Op == ssaop.OpAddr && ssa.SymIsRO(ssa.AuxToSym(v.Args[1].Aux)) {
    63  								break
    64  							}
    65  							fallthrough
    66  						default:
    67  							// CALL, DUFFCOPY, etc. are both
    68  							// reads and writes.
    69  							loadUse.Add(a.ID)
    70  						}
    71  					}
    72  				}
    73  			} else {
    74  				if v.Op == ssaop.OpLocalAddr {
    75  					if _, ok := localAddrs[v.Aux]; !ok {
    76  						localAddrs[v.Aux] = v
    77  					}
    78  					continue
    79  				}
    80  				if v.Op == ssaop.OpInlMark || v.Op == ssaop.OpConvert {
    81  					// Not really a use of the memory. See #67957.
    82  					continue
    83  				}
    84  				for _, a := range v.Args {
    85  					if a.Block == b && a.Type.IsMemory() {
    86  						loadUse.Add(a.ID)
    87  					}
    88  				}
    89  			}
    90  		}
    91  		if len(stores) == 0 {
    92  			continue
    93  		}
    94  
    95  		// find last store in the block
    96  		var last *ssa.Value
    97  		for _, v := range stores {
    98  			if storeUse.Contains(v.ID) {
    99  				continue
   100  			}
   101  			if last != nil {
   102  				b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
   103  			}
   104  			last = v
   105  		}
   106  		if last == nil {
   107  			b.Fatalf("no last store found - cycle?")
   108  		}
   109  
   110  		// Walk backwards looking for dead stores. Keep track of shadowed addresses.
   111  		// A "shadowed address" is a pointer, offset, and size describing a memory region that
   112  		// is known to be written. We keep track of shadowed addresses in the shadowed map,
   113  		// mapping the ID of the address to a shadowRanges where future writes will happen.
   114  		// Since we're walking backwards, writes to a shadowed region are useless,
   115  		// as they will be immediately overwritten.
   116  		shadowed.Clear()
   117  		shadowedRanges = shadowedRanges[:0]
   118  		v := last
   119  
   120  	walkloop:
   121  		if loadUse.Contains(v.ID) {
   122  			// Someone might be reading this memory state.
   123  			// Clear all shadowed addresses.
   124  			shadowed.Clear()
   125  			shadowedRanges = shadowedRanges[:0]
   126  		}
   127  		if v.Op == ssaop.OpStore || v.Op == ssaop.OpZero || v.Op == ssaop.OpMove {
   128  			ptr := v.Args[0]
   129  			var off int64
   130  			for ptr.Op == ssaop.OpOffPtr { // Walk to base pointer
   131  				off += ptr.AuxInt
   132  				ptr = ptr.Args[0]
   133  			}
   134  			var sz int64
   135  			switch v.Op {
   136  			case ssaop.OpStore:
   137  				sz = v.Aux.(*types.Type).Size()
   138  			case ssaop.OpZero, ssaop.OpMove:
   139  				sz = v.AuxInt
   140  			}
   141  			if ptr.Op == ssaop.OpLocalAddr {
   142  				if la, ok := localAddrs[ptr.Aux]; ok {
   143  					ptr = la
   144  				}
   145  			}
   146  			var si *shadowRanges
   147  			idx, ok := shadowed.Get(ptr.ID)
   148  			if ok {
   149  				// The sparseMap stores a 1-based index, so we subtract 1.
   150  				si = shadowedRanges[idx-1]
   151  			}
   152  
   153  			if si != nil && si.contains(off, off+sz) {
   154  				// Modify the store/zero/move into a copy of the memory state,
   155  				// effectively eliding the store operation.
   156  				if v.Op == ssaop.OpStore || v.Op == ssaop.OpMove {
   157  					//    Store addr value mem
   158  					// or  Move dst src mem
   159  					v.SetArgs1(v.Args[2])
   160  				} else {
   161  					// Zero addr mem
   162  					v.SetArgs1(v.Args[1])
   163  				}
   164  				v.Aux = nil
   165  				v.AuxInt = 0
   166  				v.Op = ssaop.OpCopy
   167  			} else {
   168  				// Extend shadowed region.
   169  				if si == nil {
   170  					si = &shadowRanges{}
   171  					shadowedRanges = append(shadowedRanges, si)
   172  					// Store a 1-based index in the sparseMap.
   173  					shadowed.Set(ptr.ID, int32(len(shadowedRanges)))
   174  				}
   175  				si.add(off, off+sz)
   176  			}
   177  		}
   178  		// walk to previous store
   179  		if v.Op == ssaop.OpPhi {
   180  			// At start of block.  Move on to next block.
   181  			// The memory phi, if it exists, is always
   182  			// the first logical store in the block.
   183  			// (Even if it isn't the first in the current b.Values order.)
   184  			continue
   185  		}
   186  		for _, a := range v.Args {
   187  			if a.Block == b && a.Type.IsMemory() {
   188  				v = a
   189  				goto walkloop
   190  			}
   191  		}
   192  	}
   193  }
   194  
   195  // shadowRange represents a single byte range [lo,hi] that will be written.
   196  type shadowRange struct {
   197  	lo, hi uint16
   198  }
   199  
   200  // shadowRanges stores an unordered collection of disjoint byte ranges.
   201  type shadowRanges struct {
   202  	ranges []shadowRange
   203  }
   204  
   205  // contains reports whether [lo:hi] is completely within sr.
   206  func (sr *shadowRanges) contains(lo, hi int64) bool {
   207  	for _, r := range sr.ranges {
   208  		if lo >= int64(r.lo) && hi <= int64(r.hi) {
   209  			return true
   210  		}
   211  	}
   212  	return false
   213  }
   214  
   215  func (sr *shadowRanges) add(lo, hi int64) {
   216  	// Ignore the store if:
   217  	// - the range doesn't fit in 16 bits, or
   218  	// - we already track maxShadowRanges intervals.
   219  	// The cap prevents a theoretical O(n^2) blow-up.
   220  	if lo < 0 || hi > 0xffff || len(sr.ranges) >= maxShadowRanges {
   221  		return
   222  	}
   223  	nlo := lo
   224  	nhi := hi
   225  	out := sr.ranges[:0]
   226  
   227  	for _, r := range sr.ranges {
   228  		if nhi < int64(r.lo) || nlo > int64(r.hi) {
   229  			out = append(out, r)
   230  			continue
   231  		}
   232  		if int64(r.lo) < nlo {
   233  			nlo = int64(r.lo)
   234  		}
   235  		if int64(r.hi) > nhi {
   236  			nhi = int64(r.hi)
   237  		}
   238  	}
   239  	sr.ranges = append(out, shadowRange{uint16(nlo), uint16(nhi)})
   240  }
   241  
   242  // elimDeadAutosGeneric deletes autos that are never accessed. To achieve this
   243  // we track the operations that the address of each auto reaches and if it only
   244  // reaches stores then we delete all the stores. The other operations will then
   245  // be eliminated by the dead code elimination pass.
   246  func elimDeadAutosGeneric(f *ssa.Func) {
   247  	addr := make(map[*ssa.Value]*ir.Name) // values that the address of the auto reaches
   248  	elim := make(map[*ssa.Value]*ir.Name) // values that could be eliminated if the auto is
   249  	move := make(map[*ir.Name]ir.NameSet) // for a (Move &y &x _) and y is unused, move[y].Add(x)
   250  	var used ir.NameSet                   // used autos that must be kept
   251  
   252  	// Adds a name to used and, when it is the target of a move, also
   253  	// propagates the used state to its source.
   254  	var usedAdd func(n *ir.Name) bool
   255  	usedAdd = func(n *ir.Name) bool {
   256  		if used.Has(n) {
   257  			return false
   258  		}
   259  		used.Add(n)
   260  		if s := move[n]; s != nil {
   261  			delete(move, n)
   262  			for n := range s {
   263  				usedAdd(n)
   264  			}
   265  		}
   266  		return true
   267  	}
   268  
   269  	// visit the value and report whether any of the maps are updated
   270  	visit := func(v *ssa.Value) (changed bool) {
   271  		args := v.Args
   272  		switch v.Op {
   273  		case ssaop.OpAddr, ssaop.OpLocalAddr:
   274  			// Propagate the address if it points to an auto.
   275  			n, ok := v.Aux.(*ir.Name)
   276  			if !ok || (n.Class != ir.PAUTO && !isABIInternalParam(f, n)) {
   277  				return
   278  			}
   279  			if addr[v] == nil {
   280  				addr[v] = n
   281  				changed = true
   282  			}
   283  			return
   284  		case ssaop.OpVarDef:
   285  			// v should be eliminated if we eliminate the auto.
   286  			n, ok := v.Aux.(*ir.Name)
   287  			if !ok || (n.Class != ir.PAUTO && !isABIInternalParam(f, n)) {
   288  				return
   289  			}
   290  			if elim[v] == nil {
   291  				elim[v] = n
   292  				changed = true
   293  			}
   294  			return
   295  		case ssaop.OpVarLive:
   296  			// Don't delete the auto if it needs to be kept alive.
   297  
   298  			// We depend on this check to keep the autotmp stack slots
   299  			// for open-coded defers from being removed (since they
   300  			// may not be used by the inline code, but will be used by
   301  			// panic processing).
   302  			n, ok := v.Aux.(*ir.Name)
   303  			if !ok || (n.Class != ir.PAUTO && !isABIInternalParam(f, n)) {
   304  				return
   305  			}
   306  			changed = usedAdd(n) || changed
   307  			return
   308  		case ssaop.OpStore, ssaop.OpMove, ssaop.OpZero:
   309  			// v should be eliminated if we eliminate the auto.
   310  			n, ok := addr[args[0]]
   311  			if ok && elim[v] == nil {
   312  				elim[v] = n
   313  				changed = true
   314  			}
   315  			// Other args might hold pointers to autos.
   316  			args = args[1:]
   317  		}
   318  
   319  		// The code below assumes that we have handled all the ops
   320  		// with sym effects already. Sanity check that here.
   321  		// Ignore Args since they can't be autos.
   322  		if v.Op.SymEffect() != ssaop.SymNone && v.Op != ssaop.OpArg {
   323  			panic("unhandled op with sym effect")
   324  		}
   325  
   326  		if v.Uses == 0 && v.Op != ssaop.OpNilCheck && !v.Op.IsCall() && !v.Op.HasSideEffects() || len(args) == 0 {
   327  			// We need to keep nil checks even if they have no use.
   328  			// Also keep calls and values that have side effects.
   329  			return
   330  		}
   331  
   332  		// If the address of the auto reaches a memory or control
   333  		// operation not covered above then we probably need to keep it.
   334  		// We also need to keep autos if they reach Phis (issue #26153).
   335  		if v.Type.IsMemory() || v.Type.IsFlags() || v.Op == ssaop.OpPhi || v.MemoryArg() != nil {
   336  			for _, a := range args {
   337  				if n, ok := addr[a]; ok {
   338  					// If the addr of n is used by an OpMove as its source arg,
   339  					// and the OpMove's target arg is the addr of a unused name,
   340  					// then temporarily treat n as unused, and record in move map.
   341  					if nam, ok := elim[v]; ok && v.Op == ssaop.OpMove && !used.Has(nam) {
   342  						if used.Has(n) {
   343  							continue
   344  						}
   345  						s := move[nam]
   346  						if s == nil {
   347  							s = ir.NameSet{}
   348  							move[nam] = s
   349  						}
   350  						s.Add(n)
   351  						continue
   352  					}
   353  					changed = usedAdd(n) || changed
   354  				}
   355  			}
   356  			return
   357  		}
   358  
   359  		// Propagate any auto addresses through v.
   360  		var node *ir.Name
   361  		for _, a := range args {
   362  			if n, ok := addr[a]; ok {
   363  				if node == nil {
   364  					if !used.Has(n) {
   365  						node = n
   366  					}
   367  				} else {
   368  					if node == n {
   369  						continue
   370  					}
   371  					// Most of the time we only see one pointer
   372  					// reaching an op, but some ops can take
   373  					// multiple pointers (e.g. NeqPtr, Phi etc.).
   374  					// This is rare, so just propagate the first
   375  					// value to keep things simple.
   376  					changed = usedAdd(n) || changed
   377  				}
   378  			}
   379  		}
   380  		if node == nil {
   381  			return
   382  		}
   383  		if addr[v] == nil {
   384  			// The address of an auto reaches this op.
   385  			addr[v] = node
   386  			changed = true
   387  			return
   388  		}
   389  		if addr[v] != node {
   390  			// This doesn't happen in practice, but catch it just in case.
   391  			changed = usedAdd(node) || changed
   392  		}
   393  		return
   394  	}
   395  
   396  	iterations := 0
   397  	for {
   398  		if iterations == 4 {
   399  			// give up
   400  			return
   401  		}
   402  		iterations++
   403  		changed := false
   404  		for _, b := range f.Blocks {
   405  			for _, v := range b.Values {
   406  				changed = visit(v) || changed
   407  			}
   408  			// keep the auto if its address reaches a control value
   409  			for _, c := range b.ControlValues() {
   410  				if n, ok := addr[c]; ok {
   411  					changed = usedAdd(n) || changed
   412  				}
   413  			}
   414  		}
   415  		if !changed {
   416  			break
   417  		}
   418  	}
   419  
   420  	// Eliminate stores to unread autos.
   421  	for v, n := range elim {
   422  		if used.Has(n) {
   423  			continue
   424  		}
   425  		// replace with OpCopy
   426  		v.SetArgs1(v.MemoryArg())
   427  		v.Aux = nil
   428  		v.AuxInt = 0
   429  		v.Op = ssaop.OpCopy
   430  	}
   431  }
   432  
   433  // elimUnreadAutos deletes stores (and associated bookkeeping ops VarDef and VarKill)
   434  // to autos that are never read from.
   435  func elimUnreadAutos(f *ssa.Func) {
   436  	// Loop over all ops that affect autos taking note of which
   437  	// autos we need and also stores that we might be able to
   438  	// eliminate.
   439  	var seen ir.NameSet
   440  	var stores []*ssa.Value
   441  	for _, b := range f.Blocks {
   442  		for _, v := range b.Values {
   443  			n, ok := v.Aux.(*ir.Name)
   444  			if !ok {
   445  				continue
   446  			}
   447  			if n.Class != ir.PAUTO && !isABIInternalParam(f, n) {
   448  				continue
   449  			}
   450  
   451  			effect := v.Op.SymEffect()
   452  			switch effect {
   453  			case ssaop.SymNone, ssaop.SymWrite:
   454  				// If we haven't seen the auto yet
   455  				// then this might be a store we can
   456  				// eliminate.
   457  				if !seen.Has(n) {
   458  					stores = append(stores, v)
   459  				}
   460  			default:
   461  				// Assume the auto is needed (loaded,
   462  				// has its address taken, etc.).
   463  				// Note we have to check the uses
   464  				// because dead loads haven't been
   465  				// eliminated yet.
   466  				if v.Uses > 0 {
   467  					seen.Add(n)
   468  				}
   469  			}
   470  		}
   471  	}
   472  
   473  	// Eliminate stores to unread autos.
   474  	for _, store := range stores {
   475  		n, _ := store.Aux.(*ir.Name)
   476  		if seen.Has(n) {
   477  			continue
   478  		}
   479  
   480  		// replace store with OpCopy
   481  		store.SetArgs1(store.MemoryArg())
   482  		store.Aux = nil
   483  		store.AuxInt = 0
   484  		store.Op = ssaop.OpCopy
   485  	}
   486  }
   487  
   488  // isABIInternalParam returns whether n is a parameter of an ABIInternal
   489  // function. For dead store elimination, we can treat parameters the same
   490  // way as autos. Storing to a parameter can be removed if it is not read
   491  // or address-taken.
   492  //
   493  // We check ABI here because for a cgo_unsafe_arg function (which is ABI0),
   494  // all the args are effectively address-taken, but not necessarily have
   495  // an Addr or LocalAddr op. We could probably just check for cgo_unsafe_arg,
   496  // but ABIInternal is mostly what matters.
   497  func isABIInternalParam(f *ssa.Func, n *ir.Name) bool {
   498  	return n.Class == ir.PPARAM && f.ABISelf.Which() == obj.ABIInternal
   499  }
   500
View as plain text