diff options
author | Keith Randall <khr@golang.org> | 2015-05-26 14:43:25 -0700 |
---|---|---|
committer | Keith Randall <khr@golang.org> | 2015-06-04 23:03:41 +0000 |
commit | 8d32360bddaafb4e8eafe0e57065b4883b4ec55f (patch) | |
tree | bd509f72447a920881188b023dabc2bbe8c90e76 /src/cmd/compile/internal/ssa/deadstore.go | |
parent | 1114a76ae6081242c38614aeb4ff9c37b8be75c4 (diff) | |
download | go-8d32360bddaafb4e8eafe0e57065b4883b4ec55f.tar.gz go-8d32360bddaafb4e8eafe0e57065b4883b4ec55f.zip |
[dev.ssa] cmd/internal/ssa: add deadstore pass
Eliminate dead stores. Dead stores are those which are
unconditionally followed by another store to the same location, with
no intervening load.
Just a simple intra-block implementation for now.
Change-Id: I2bf54e3a342608fc4e01edbe1b429e83f24764ab
Reviewed-on: https://go-review.googlesource.com/10386
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Diffstat (limited to 'src/cmd/compile/internal/ssa/deadstore.go')
-rw-r--r-- | src/cmd/compile/internal/ssa/deadstore.go | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/deadstore.go b/src/cmd/compile/internal/ssa/deadstore.go new file mode 100644 index 0000000000..b02b35460a --- /dev/null +++ b/src/cmd/compile/internal/ssa/deadstore.go @@ -0,0 +1,103 @@ +// 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 "log" + +// 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 := newSparseSet(f.NumValues()) + storeUse := newSparseSet(f.NumValues()) + shadowed := newSparseSet(f.NumValues()) + 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 { + // 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 { + log.Fatalf("two final stores - simultaneous live stores", last, v) + } + last = v + } + if last == nil { + log.Fatalf("no last store found - cycle?") + } + + // Walk backwards looking for dead stores. Keep track of shadowed addresses. + // An "address" is an SSA Value which encodes both the address and size of + // the write. This code will not remove dead stores to the same address + // of different types. + 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 { + if shadowed.contains(v.Args[0].ID) { + // Modify store into a copy + v.Op = OpCopy + v.Aux = nil + v.SetArgs1(v.Args[2]) + } else { + shadowed.add(v.Args[0].ID) + } + } + // walk to previous store + if v.Op == OpPhi { + continue // At start of block. Move on to next block. + } + for _, a := range v.Args { + if a.Block == b && a.Type.IsMemory() { + v = a + goto walkloop + } + } + } +} |