src/cmd/compile/internal/ssa/deadstore.go - go - Git at Google

 // Copyright 2015 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package ssa

 import (
 	"cmd/compile/internal/ir"
 	"cmd/compile/internal/types"
 )

 // dse does dead-store elimination on the Function.
 // Dead stores are those which are unconditionally followed by
 // another store to the same location, with no intervening load.
 // This implementation only works within a basic block. TODO: use something more global.
 func dse(f *Func) {
 	var stores []*Value
 	loadUse := f.newSparseSet(f.NumValues())
 	defer f.retSparseSet(loadUse)
 	storeUse := f.newSparseSet(f.NumValues())
 	defer f.retSparseSet(storeUse)
 	shadowed := f.newSparseMap(f.NumValues())
 	defer f.retSparseMap(shadowed)
 	for _, b := range f.Blocks {
 		// Find all the stores in this block. Categorize their uses:
 		//  loadUse contains stores which are used by a subsequent load.
 		//  storeUse contains stores which are used by a subsequent store.
 		loadUse.clear()
 		storeUse.clear()
 		stores = stores[:0]
 		for _, v := range b.Values {
 			if v.Op == OpPhi {
 				// Ignore phis - they will always be first and can't be eliminated
 				continue
 			}
 			if v.Type.IsMemory() {
 				stores = append(stores, v)
 				for _, a := range v.Args {
 					if a.Block == b && a.Type.IsMemory() {
 						storeUse.add(a.ID)
 						if v.Op != OpStore && v.Op != OpZero && v.Op != OpVarDef {
 							// CALL, DUFFCOPY, etc. are both
 							// reads and writes.
 							loadUse.add(a.ID)
 						}
 					}
 				}
 			} else {
 				for _, a := range v.Args {
 					if a.Block == b && a.Type.IsMemory() {
 						loadUse.add(a.ID)
 					}
 				}
 			}
 		}
 		if len(stores) == 0 {
 			continue
 		}

 		// find last store in the block
 		var last *Value
 		for _, v := range stores {
 			if storeUse.contains(v.ID) {
 				continue
 			}
 			if last != nil {
 				b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
 			}
 			last = v
 		}
 		if last == nil {
 			b.Fatalf("no last store found - cycle?")
 		}

 		// Walk backwards looking for dead stores. Keep track of shadowed addresses.
 		// A "shadowed address" is a pointer, offset, and size describing a memory region that
 		// is known to be written. We keep track of shadowed addresses in the shadowed map,
 		// mapping the ID of the address to a shadowRange where future writes will happen.
 		// Since we're walking backwards, writes to a shadowed region are useless,
 		// as they will be immediately overwritten.
 		shadowed.clear()
 		v := last

 	walkloop:
 		if loadUse.contains(v.ID) {
 			// Someone might be reading this memory state.
 			// Clear all shadowed addresses.
 			shadowed.clear()
 		}
 		if v.Op == OpStore || v.Op == OpZero {
 			ptr := v.Args[0]
 			var off int64
 			for ptr.Op == OpOffPtr { // Walk to base pointer
 				off += ptr.AuxInt
 				ptr = ptr.Args[0]
 			}
 			var sz int64
 			if v.Op == OpStore {
 				sz = v.Aux.(*types.Type).Size()
 			} else { // OpZero
 				sz = v.AuxInt
 			}
 			sr := shadowRange(shadowed.get(ptr.ID))
 			if sr.contains(off, off+sz) {
 				// Modify the store/zero into a copy of the memory state,
 				// effectively eliding the store operation.
 				if v.Op == OpStore {
 					// store addr value mem
 					v.SetArgs1(v.Args[2])
 				} else {
 					// zero addr mem
 					v.SetArgs1(v.Args[1])
 				}
 				v.Aux = nil
 				v.AuxInt = 0
 				v.Op = OpCopy
 			} else {
 				// Extend shadowed region.
 				shadowed.set(ptr.ID, int32(sr.merge(off, off+sz)))
 			}
 		}
 		// walk to previous store
 		if v.Op == OpPhi {
 			// At start of block.  Move on to next block.
 			// The memory phi, if it exists, is always
 			// the first logical store in the block.
 			// (Even if it isn't the first in the current b.Values order.)
 			continue
 		}
 		for _, a := range v.Args {
 			if a.Block == b && a.Type.IsMemory() {
 				v = a
 				goto walkloop
 			}
 		}
 	}
 }

 // A shadowRange encodes a set of byte offsets [lo():hi()] from
 // a given pointer that will be written to later in the block.
 // A zero shadowRange encodes an empty shadowed range (and so
 // does a -1 shadowRange, which is what sparsemap.get returns
 // on a failed lookup).
 type shadowRange int32

 func (sr shadowRange) lo() int64 {
 	return int64(sr & 0xffff)
 }
 func (sr shadowRange) hi() int64 {
 	return int64((sr >> 16) & 0xffff)
 }

 // contains reports whether [lo:hi] is completely within sr.
 func (sr shadowRange) contains(lo, hi int64) bool {
 	return lo >= sr.lo() && hi <= sr.hi()
 }

 // merge returns the union of sr and [lo:hi].
 // merge is allowed to return something smaller than the union.
 func (sr shadowRange) merge(lo, hi int64) shadowRange {
 	if lo < 0 || hi > 0xffff {
 		// Ignore offsets that are too large or small.
 		return sr
 	}
 	if sr.lo() == sr.hi() {
 		// Old range is empty - use new one.
 		return shadowRange(lo + hi<<16)
 	}
 	if hi < sr.lo() || lo > sr.hi() {
 		// The two regions don't overlap or abut, so we would
 		// have to keep track of multiple disjoint ranges.
 		// Because we can only keep one, keep the larger one.
 		if sr.hi()-sr.lo() >= hi-lo {
 			return sr
 		}
 		return shadowRange(lo + hi<<16)
 	}
 	// Regions overlap or abut - compute the union.
 	return shadowRange(min(lo, sr.lo()) + max(hi, sr.hi())<<16)
 }

 // elimDeadAutosGeneric deletes autos that are never accessed. To achieve this
 // we track the operations that the address of each auto reaches and if it only
 // reaches stores then we delete all the stores. The other operations will then
 // be eliminated by the dead code elimination pass.
 func elimDeadAutosGeneric(f *Func) {
 	addr := make(map[*Value]*ir.Name) // values that the address of the auto reaches
 	elim := make(map[*Value]*ir.Name) // values that could be eliminated if the auto is
 	var used ir.NameSet               // used autos that must be kept

 	// visit the value and report whether any of the maps are updated
 	visit := func(v *Value) (changed bool) {
 		args := v.Args
 		switch v.Op {
 		case OpAddr, OpLocalAddr:
 			// Propagate the address if it points to an auto.
 			n, ok := v.Aux.(*ir.Name)
 			if !ok || n.Class != ir.PAUTO {
 				return
 			}
 			if addr[v] == nil {
 				addr[v] = n
 				changed = true
 			}
 			return
 		case OpVarDef:
 			// v should be eliminated if we eliminate the auto.
 			n, ok := v.Aux.(*ir.Name)
 			if !ok || n.Class != ir.PAUTO {
 				return
 			}
 			if elim[v] == nil {
 				elim[v] = n
 				changed = true
 			}
 			return
 		case OpVarLive:
 			// Don't delete the auto if it needs to be kept alive.

 			// We depend on this check to keep the autotmp stack slots
 			// for open-coded defers from being removed (since they
 			// may not be used by the inline code, but will be used by
 			// panic processing).
 			n, ok := v.Aux.(*ir.Name)
 			if !ok || n.Class != ir.PAUTO {
 				return
 			}
 			if !used.Has(n) {
 				used.Add(n)
 				changed = true
 			}
 			return
 		case OpStore, OpMove, OpZero:
 			// v should be eliminated if we eliminate the auto.
 			n, ok := addr[args[0]]
 			if ok && elim[v] == nil {
 				elim[v] = n
 				changed = true
 			}
 			// Other args might hold pointers to autos.
 			args = args[1:]
 		}

 		// The code below assumes that we have handled all the ops
 		// with sym effects already. Sanity check that here.
 		// Ignore Args since they can't be autos.
 		if v.Op.SymEffect() != SymNone && v.Op != OpArg {
 			panic("unhandled op with sym effect")
 		}

 		if v.Uses == 0 && v.Op != OpNilCheck && !v.Op.IsCall() && !v.Op.HasSideEffects() || len(args) == 0 {
 			// We need to keep nil checks even if they have no use.
 			// Also keep calls and values that have side effects.
 			return
 		}

 		// If the address of the auto reaches a memory or control
 		// operation not covered above then we probably need to keep it.
 		// We also need to keep autos if they reach Phis (issue #26153).
 		if v.Type.IsMemory() || v.Type.IsFlags() || v.Op == OpPhi || v.MemoryArg() != nil {
 			for _, a := range args {
 				if n, ok := addr[a]; ok {
 					if !used.Has(n) {
 						used.Add(n)
 						changed = true
 					}
 				}
 			}
 			return
 		}

 		// Propagate any auto addresses through v.
 		var node *ir.Name
 		for _, a := range args {
 			if n, ok := addr[a]; ok && !used.Has(n) {
 				if node == nil {
 					node = n
 				} else if node != n {
 					// Most of the time we only see one pointer
 					// reaching an op, but some ops can take
 					// multiple pointers (e.g. NeqPtr, Phi etc.).
 					// This is rare, so just propagate the first
 					// value to keep things simple.
 					used.Add(n)
 					changed = true
 				}
 			}
 		}
 		if node == nil {
 			return
 		}
 		if addr[v] == nil {
 			// The address of an auto reaches this op.
 			addr[v] = node
 			changed = true
 			return
 		}
 		if addr[v] != node {
 			// This doesn't happen in practice, but catch it just in case.
 			used.Add(node)
 			changed = true
 		}
 		return
 	}

 	iterations := 0
 	for {
 		if iterations == 4 {
 			// give up
 			return
 		}
 		iterations++
 		changed := false
 		for _, b := range f.Blocks {
 			for _, v := range b.Values {
 				changed = visit(v) || changed
 			}
 			// keep the auto if its address reaches a control value
 			for _, c := range b.ControlValues() {
 				if n, ok := addr[c]; ok && !used.Has(n) {
 					used.Add(n)
 					changed = true
 				}
 			}
 		}
 		if !changed {
 			break
 		}
 	}

 	// Eliminate stores to unread autos.
 	for v, n := range elim {
 		if used.Has(n) {
 			continue
 		}
 		// replace with OpCopy
 		v.SetArgs1(v.MemoryArg())
 		v.Aux = nil
 		v.AuxInt = 0
 		v.Op = OpCopy
 	}
 }

 // elimUnreadAutos deletes stores (and associated bookkeeping ops VarDef and VarKill)
 // to autos that are never read from.
 func elimUnreadAutos(f *Func) {
 	// Loop over all ops that affect autos taking note of which
 	// autos we need and also stores that we might be able to
 	// eliminate.
 	var seen ir.NameSet
 	var stores []*Value
 	for _, b := range f.Blocks {
 		for _, v := range b.Values {
 			n, ok := v.Aux.(*ir.Name)
 			if !ok {
 				continue
 			}
 			if n.Class != ir.PAUTO {
 				continue
 			}

 			effect := v.Op.SymEffect()
 			switch effect {
 			case SymNone, SymWrite:
 				// If we haven't seen the auto yet
 				// then this might be a store we can
 				// eliminate.
 				if !seen.Has(n) {
 					stores = append(stores, v)
 				}
 			default:
 				// Assume the auto is needed (loaded,
 				// has its address taken, etc.).
 				// Note we have to check the uses
 				// because dead loads haven't been
 				// eliminated yet.
 				if v.Uses > 0 {
 					seen.Add(n)
 				}
 			}
 		}
 	}

 	// Eliminate stores to unread autos.
 	for _, store := range stores {
 		n, _ := store.Aux.(*ir.Name)
 		if seen.Has(n) {
 			continue
 		}

 		// replace store with OpCopy
 		store.SetArgs1(store.MemoryArg())
 		store.Aux = nil
 		store.AuxInt = 0
 		store.Op = OpCopy
 	}
 }
	// Copyright 2015 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package ssa

	import (
	"cmd/compile/internal/ir"
	"cmd/compile/internal/types"
	)

	// dse does dead-store elimination on the Function.
	// Dead stores are those which are unconditionally followed by
	// another store to the same location, with no intervening load.
	// This implementation only works within a basic block. TODO: use something more global.
	func dse(f *Func) {
	var stores []*Value
	loadUse := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(loadUse)
	storeUse := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(storeUse)
	shadowed := f.newSparseMap(f.NumValues())
	defer f.retSparseMap(shadowed)
	for _, b := range f.Blocks {
	// Find all the stores in this block. Categorize their uses:
	// loadUse contains stores which are used by a subsequent load.
	// storeUse contains stores which are used by a subsequent store.
	loadUse.clear()
	storeUse.clear()
	stores = stores[:0]
	for _, v := range b.Values {
	if v.Op == OpPhi {
	// Ignore phis - they will always be first and can't be eliminated
	continue
	}
	if v.Type.IsMemory() {
	stores = append(stores, v)
	for _, a := range v.Args {
	if a.Block == b && a.Type.IsMemory() {
	storeUse.add(a.ID)
	if v.Op != OpStore && v.Op != OpZero && v.Op != OpVarDef {
	// CALL, DUFFCOPY, etc. are both
	// reads and writes.
	loadUse.add(a.ID)
	}
	}
	}
	} else {
	for _, a := range v.Args {
	if a.Block == b && a.Type.IsMemory() {
	loadUse.add(a.ID)
	}
	}
	}
	}
	if len(stores) == 0 {
	continue
	}

	// find last store in the block
	var last *Value
	for _, v := range stores {
	if storeUse.contains(v.ID) {
	continue
	}
	if last != nil {
	b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
	}
	last = v
	}
	if last == nil {
	b.Fatalf("no last store found - cycle?")
	}

	// Walk backwards looking for dead stores. Keep track of shadowed addresses.
	// A "shadowed address" is a pointer, offset, and size describing a memory region that
	// is known to be written. We keep track of shadowed addresses in the shadowed map,
	// mapping the ID of the address to a shadowRange where future writes will happen.
	// Since we're walking backwards, writes to a shadowed region are useless,
	// as they will be immediately overwritten.
	shadowed.clear()
	v := last

	walkloop:
	if loadUse.contains(v.ID) {
	// Someone might be reading this memory state.
	// Clear all shadowed addresses.
	shadowed.clear()
	}
	if v.Op == OpStore \|\| v.Op == OpZero {
	ptr := v.Args[0]
	var off int64
	for ptr.Op == OpOffPtr { // Walk to base pointer
	off += ptr.AuxInt
	ptr = ptr.Args[0]
	}
	var sz int64
	if v.Op == OpStore {
	sz = v.Aux.(*types.Type).Size()
	} else { // OpZero
	sz = v.AuxInt
	}
	sr := shadowRange(shadowed.get(ptr.ID))
	if sr.contains(off, off+sz) {
	// Modify the store/zero into a copy of the memory state,
	// effectively eliding the store operation.
	if v.Op == OpStore {
	// store addr value mem
	v.SetArgs1(v.Args[2])
	} else {
	// zero addr mem
	v.SetArgs1(v.Args[1])
	}
	v.Aux = nil
	v.AuxInt = 0
	v.Op = OpCopy
	} else {
	// Extend shadowed region.
	shadowed.set(ptr.ID, int32(sr.merge(off, off+sz)))
	}
	}
	// walk to previous store
	if v.Op == OpPhi {
	// At start of block. Move on to next block.
	// The memory phi, if it exists, is always
	// the first logical store in the block.
	// (Even if it isn't the first in the current b.Values order.)
	continue
	}
	for _, a := range v.Args {
	if a.Block == b && a.Type.IsMemory() {
	v = a
	goto walkloop
	}
	}
	}
	}

	// A shadowRange encodes a set of byte offsets [lo():hi()] from
	// a given pointer that will be written to later in the block.
	// A zero shadowRange encodes an empty shadowed range (and so
	// does a -1 shadowRange, which is what sparsemap.get returns
	// on a failed lookup).
	type shadowRange int32

	func (sr shadowRange) lo() int64 {
	return int64(sr & 0xffff)
	}
	func (sr shadowRange) hi() int64 {
	return int64((sr >> 16) & 0xffff)
	}

	// contains reports whether [lo:hi] is completely within sr.
	func (sr shadowRange) contains(lo, hi int64) bool {
	return lo >= sr.lo() && hi <= sr.hi()
	}

	// merge returns the union of sr and [lo:hi].
	// merge is allowed to return something smaller than the union.
	func (sr shadowRange) merge(lo, hi int64) shadowRange {
	if lo < 0 \|\| hi > 0xffff {
	// Ignore offsets that are too large or small.
	return sr
	}
	if sr.lo() == sr.hi() {
	// Old range is empty - use new one.
	return shadowRange(lo + hi<<16)
	}
	if hi < sr.lo() \|\| lo > sr.hi() {
	// The two regions don't overlap or abut, so we would
	// have to keep track of multiple disjoint ranges.
	// Because we can only keep one, keep the larger one.
	if sr.hi()-sr.lo() >= hi-lo {
	return sr
	}
	return shadowRange(lo + hi<<16)
	}
	// Regions overlap or abut - compute the union.
	return shadowRange(min(lo, sr.lo()) + max(hi, sr.hi())<<16)
	}

	// elimDeadAutosGeneric deletes autos that are never accessed. To achieve this
	// we track the operations that the address of each auto reaches and if it only
	// reaches stores then we delete all the stores. The other operations will then
	// be eliminated by the dead code elimination pass.
	func elimDeadAutosGeneric(f *Func) {
	addr := make(map[Value]ir.Name) // values that the address of the auto reaches
	elim := make(map[Value]ir.Name) // values that could be eliminated if the auto is
	var used ir.NameSet // used autos that must be kept

	// visit the value and report whether any of the maps are updated
	visit := func(v *Value) (changed bool) {
	args := v.Args
	switch v.Op {
	case OpAddr, OpLocalAddr:
	// Propagate the address if it points to an auto.
	n, ok := v.Aux.(*ir.Name)
	if !ok \|\| n.Class != ir.PAUTO {
	return
	}
	if addr[v] == nil {
	addr[v] = n
	changed = true
	}
	return
	case OpVarDef:
	// v should be eliminated if we eliminate the auto.
	n, ok := v.Aux.(*ir.Name)
	if !ok \|\| n.Class != ir.PAUTO {
	return
	}
	if elim[v] == nil {
	elim[v] = n
	changed = true
	}
	return
	case OpVarLive:
	// Don't delete the auto if it needs to be kept alive.

	// We depend on this check to keep the autotmp stack slots
	// for open-coded defers from being removed (since they
	// may not be used by the inline code, but will be used by
	// panic processing).
	n, ok := v.Aux.(*ir.Name)
	if !ok \|\| n.Class != ir.PAUTO {
	return
	}
	if !used.Has(n) {
	used.Add(n)
	changed = true
	}
	return
	case OpStore, OpMove, OpZero:
	// v should be eliminated if we eliminate the auto.
	n, ok := addr[args[0]]
	if ok && elim[v] == nil {
	elim[v] = n
	changed = true
	}
	// Other args might hold pointers to autos.
	args = args[1:]
	}

	// The code below assumes that we have handled all the ops
	// with sym effects already. Sanity check that here.
	// Ignore Args since they can't be autos.
	if v.Op.SymEffect() != SymNone && v.Op != OpArg {
	panic("unhandled op with sym effect")
	}

	if v.Uses == 0 && v.Op != OpNilCheck && !v.Op.IsCall() && !v.Op.HasSideEffects() \|\| len(args) == 0 {
	// We need to keep nil checks even if they have no use.
	// Also keep calls and values that have side effects.
	return
	}

	// If the address of the auto reaches a memory or control
	// operation not covered above then we probably need to keep it.
	// We also need to keep autos if they reach Phis (issue #26153).
	if v.Type.IsMemory() \|\| v.Type.IsFlags() \|\| v.Op == OpPhi \|\| v.MemoryArg() != nil {
	for _, a := range args {
	if n, ok := addr[a]; ok {
	if !used.Has(n) {
	used.Add(n)
	changed = true
	}
	}
	}
	return
	}

	// Propagate any auto addresses through v.
	var node *ir.Name
	for _, a := range args {
	if n, ok := addr[a]; ok && !used.Has(n) {
	if node == nil {
	node = n
	} else if node != n {
	// Most of the time we only see one pointer
	// reaching an op, but some ops can take
	// multiple pointers (e.g. NeqPtr, Phi etc.).
	// This is rare, so just propagate the first
	// value to keep things simple.
	used.Add(n)
	changed = true
	}
	}
	}
	if node == nil {
	return
	}
	if addr[v] == nil {
	// The address of an auto reaches this op.
	addr[v] = node
	changed = true
	return
	}
	if addr[v] != node {
	// This doesn't happen in practice, but catch it just in case.
	used.Add(node)
	changed = true
	}
	return
	}

	iterations := 0
	for {
	if iterations == 4 {
	// give up
	return
	}
	iterations++
	changed := false
	for _, b := range f.Blocks {
	for _, v := range b.Values {
	changed = visit(v) \|\| changed
	}
	// keep the auto if its address reaches a control value
	for _, c := range b.ControlValues() {
	if n, ok := addr[c]; ok && !used.Has(n) {
	used.Add(n)
	changed = true
	}
	}
	}
	if !changed {
	break
	}
	}

	// Eliminate stores to unread autos.
	for v, n := range elim {
	if used.Has(n) {
	continue
	}
	// replace with OpCopy
	v.SetArgs1(v.MemoryArg())
	v.Aux = nil
	v.AuxInt = 0
	v.Op = OpCopy
	}
	}

	// elimUnreadAutos deletes stores (and associated bookkeeping ops VarDef and VarKill)
	// to autos that are never read from.
	func elimUnreadAutos(f *Func) {
	// Loop over all ops that affect autos taking note of which
	// autos we need and also stores that we might be able to
	// eliminate.
	var seen ir.NameSet
	var stores []*Value
	for _, b := range f.Blocks {
	for _, v := range b.Values {
	n, ok := v.Aux.(*ir.Name)
	if !ok {
	continue
	}
	if n.Class != ir.PAUTO {
	continue
	}

	effect := v.Op.SymEffect()
	switch effect {
	case SymNone, SymWrite:
	// If we haven't seen the auto yet
	// then this might be a store we can
	// eliminate.
	if !seen.Has(n) {
	stores = append(stores, v)
	}
	default:
	// Assume the auto is needed (loaded,
	// has its address taken, etc.).
	// Note we have to check the uses
	// because dead loads haven't been
	// eliminated yet.
	if v.Uses > 0 {
	seen.Add(n)
	}
	}
	}
	}

	// Eliminate stores to unread autos.
	for _, store := range stores {
	n, _ := store.Aux.(*ir.Name)
	if seen.Has(n) {
	continue
	}

	// replace store with OpCopy
	store.SetArgs1(store.MemoryArg())
	store.Aux = nil
	store.AuxInt = 0
	store.Op = OpCopy
	}
	}