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