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