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