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

View as plain text