Gecko [ 167.86.127.34 ]

Name	Size	Permission
gen	[ DIR ]	drwxr-xr-x
testdata	[ DIR ]	drwxr-xr-x
README.md	7.76 KB	-rw-r--r--
TODO	950 B	-rw-r--r--
biasedsparsemap.go	2.71 KB	-rw-r--r--
block.go	8.64 KB	-rw-r--r--
branchelim.go	11.41 KB	-rw-r--r--
branchelim_test.go	5.21 KB	-rw-r--r--
cache.go	2.46 KB	-rw-r--r--
check.go	13.9 KB	-rw-r--r--
checkbce.go	956 B	-rw-r--r--
compile.go	16.22 KB	-rw-r--r--
config.go	11.39 KB	-rw-r--r--
copyelim.go	1.82 KB	-rw-r--r--
copyelim_test.go	1.29 KB	-rw-r--r--
critical.go	3.15 KB	-rw-r--r--
cse.go	10.62 KB	-rw-r--r--
cse_test.go	4.21 KB	-rw-r--r--
deadcode.go	9.73 KB	-rw-r--r--
deadcode_test.go	3.49 KB	-rw-r--r--
deadstore.go	8.98 KB	-rw-r--r--
deadstore_test.go	4.09 KB	-rw-r--r--
debug.go	33.92 KB	-rw-r--r--
debug_test.go	28.68 KB	-rw-r--r--
decompose.go	10.91 KB	-rw-r--r--
dom.go	7.98 KB	-rw-r--r--
dom_test.go	13.34 KB	-rw-r--r--
export_test.go	5.68 KB	-rw-r--r--
flagalloc.go	5.49 KB	-rw-r--r--
func.go	22.17 KB	-rw-r--r--
func_test.go	12.85 KB	-rw-r--r--
fuse.go	5.7 KB	-rw-r--r--
fuse_test.go	5.04 KB	-rw-r--r--
html.go	29.04 KB	-rw-r--r--
id.go	576 B	-rw-r--r--
layout.go	3.56 KB	-rw-r--r--
lca.go	3.71 KB	-rw-r--r--
lca_test.go	1.65 KB	-rw-r--r--
likelyadjust.go	15.23 KB	-rw-r--r--
location.go	2.8 KB	-rw-r--r--
loopbce.go	9.85 KB	-rw-r--r--
loopreschedchecks.go	15.36 KB	-rw-r--r--
looprotate.go	2.24 KB	-rw-r--r--
lower.go	1.24 KB	-rw-r--r--
magic.go	13.42 KB	-rw-r--r--
magic_test.go	9.1 KB	-rw-r--r--
nilcheck.go	11.11 KB	-rw-r--r--
nilcheck_test.go	12.07 KB	-rw-r--r--
numberlines.go	8.44 KB	-rw-r--r--
op.go	8.74 KB	-rw-r--r--
opGen.go	839.32 KB	-rw-r--r--
opt.go	290 B	-rw-r--r--
passbm_test.go	3.14 KB	-rw-r--r--
phielim.go	1.47 KB	-rw-r--r--
phiopt.go	3.96 KB	-rw-r--r--
poset.go	37.23 KB	-rw-r--r--
poset_test.go	18.14 KB	-rw-r--r--
print.go	2.98 KB	-rw-r--r--
prove.go	36.68 KB	-rw-r--r--
redblack32.go	8.9 KB	-rw-r--r--
redblack32_test.go	5.96 KB	-rw-r--r--
regalloc.go	76.36 KB	-rw-r--r--
regalloc_test.go	6.41 KB	-rw-r--r--
rewrite.go	33.06 KB	-rw-r--r--
rewrite386.go	514.14 KB	-rw-r--r--
rewrite386splitload.go	3.7 KB	-rw-r--r--
rewriteAMD64.go	1.31 MB	-rw-r--r--
rewriteAMD64splitload.go	4.95 KB	-rw-r--r--
rewriteARM.go	538.26 KB	-rw-r--r--
rewriteARM64.go	837.68 KB	-rw-r--r--
rewriteMIPS.go	203.31 KB	-rw-r--r--
rewriteMIPS64.go	227.84 KB	-rw-r--r--
rewritePPC64.go	661.88 KB	-rw-r--r--
rewriteRISCV64.go	123.11 KB	-rw-r--r--
rewriteS390X.go	904.36 KB	-rw-r--r--
rewriteWasm.go	136.86 KB	-rw-r--r--
rewrite_test.go	3.01 KB	-rw-r--r--
rewritedec.go	10.56 KB	-rw-r--r--
rewritedec64.go	64.01 KB	-rw-r--r--
rewritedecArgs.go	6.6 KB	-rw-r--r--
rewritegeneric.go	1.09 MB	-rw-r--r--
schedule.go	13.99 KB	-rw-r--r--
schedule_test.go	2.91 KB	-rw-r--r--
shift_test.go	4.05 KB	-rw-r--r--
shortcircuit.go	3.97 KB	-rw-r--r--
shortcircuit_test.go	1.31 KB	-rw-r--r--
sizeof_test.go	855 B	-rw-r--r--
softfloat.go	1.94 KB	-rw-r--r--
sparsemap.go	1.98 KB	-rw-r--r--
sparseset.go	1.54 KB	-rw-r--r--
sparsetree.go	7.88 KB	-rw-r--r--
sparsetreemap.go	7.67 KB	-rw-r--r--
stackalloc.go	10.95 KB	-rw-r--r--
stackframe.go	290 B	-rw-r--r--
stmtlines_test.go	2.75 KB	-rw-r--r--
tighten.go	4.21 KB	-rw-r--r--
trim.go	4.24 KB	-rw-r--r--
value.go	10.71 KB	-rw-r--r--
writebarrier.go	17.92 KB	-rw-r--r--
writebarrier_test.go	1.75 KB	-rw-r--r--
xposmap.go	3.29 KB	-rw-r--r--
zcse.go	2.12 KB	-rw-r--r--
zeroextension_test.go	1.66 KB	-rw-r--r--

Code Editor : deadcode.go

// 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/internal/src"
)

// findlive returns the reachable blocks and live values in f.
// The caller should call f.retDeadcodeLive(live) when it is done with it.
func findlive(f *Func) (reachable []bool, live []bool) {
	reachable = ReachableBlocks(f)
	var order []*Value
	live, order = liveValues(f, reachable)
	f.retDeadcodeLiveOrderStmts(order)
	return
}

// ReachableBlocks returns the reachable blocks in f.
func ReachableBlocks(f *Func) []bool {
	reachable := make([]bool, f.NumBlocks())
	reachable[f.Entry.ID] = true
	p := make([]*Block, 0, 64) // stack-like worklist
	p = append(p, f.Entry)
	for len(p) > 0 {
		// Pop a reachable block
		b := p[len(p)-1]
		p = p[:len(p)-1]
		// Mark successors as reachable
		s := b.Succs
		if b.Kind == BlockFirst {
			s = s[:1]
		}
		for _, e := range s {
			c := e.b
			if int(c.ID) >= len(reachable) {
				f.Fatalf("block %s >= f.NumBlocks()=%d?", c, len(reachable))
			}
			if !reachable[c.ID] {
				reachable[c.ID] = true
				p = append(p, c) // push
			}
		}
	}
	return reachable
}

// liveValues returns the live values in f and a list of values that are eligible
// to be statements in reversed data flow order.
// The second result is used to help conserve statement boundaries for debugging.
// reachable is a map from block ID to whether the block is reachable.
// The caller should call f.retDeadcodeLive(live) and f.retDeadcodeLiveOrderStmts(liveOrderStmts)
// when they are done with the return values.
func liveValues(f *Func, reachable []bool) (live []bool, liveOrderStmts []*Value) {
	live = f.newDeadcodeLive()
	if cap(live) < f.NumValues() {
		live = make([]bool, f.NumValues())
	} else {
		live = live[:f.NumValues()]
		for i := range live {
			live[i] = false
		}
	}

liveOrderStmts = f.newDeadcodeLiveOrderStmts()
	liveOrderStmts = liveOrderStmts[:0]

// After regalloc, consider all values to be live.
	// See the comment at the top of regalloc.go and in deadcode for details.
	if f.RegAlloc != nil {
		for i := range live {
			live[i] = true
		}
		return
	}

// Record all the inline indexes we need
	var liveInlIdx map[int]bool
	pt := f.Config.ctxt.PosTable
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			i := pt.Pos(v.Pos).Base().InliningIndex()
			if i < 0 {
				continue
			}
			if liveInlIdx == nil {
				liveInlIdx = map[int]bool{}
			}
			liveInlIdx[i] = true
		}
		i := pt.Pos(b.Pos).Base().InliningIndex()
		if i < 0 {
			continue
		}
		if liveInlIdx == nil {
			liveInlIdx = map[int]bool{}
		}
		liveInlIdx[i] = true
	}

// Find all live values
	q := f.Cache.deadcode.q[:0]
	defer func() { f.Cache.deadcode.q = q }()

// Starting set: all control values of reachable blocks are live.
	// Calls are live (because callee can observe the memory state).
	for _, b := range f.Blocks {
		if !reachable[b.ID] {
			continue
		}
		for _, v := range b.ControlValues() {
			if !live[v.ID] {
				live[v.ID] = true
				q = append(q, v)
				if v.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, v)
				}
			}
		}
		for _, v := range b.Values {
			if (opcodeTable[v.Op].call || opcodeTable[v.Op].hasSideEffects) && !live[v.ID] {
				live[v.ID] = true
				q = append(q, v)
				if v.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, v)
				}
			}
			if v.Type.IsVoid() && !live[v.ID] {
				// The only Void ops are nil checks and inline marks.  We must keep these.
				if v.Op == OpInlMark && !liveInlIdx[int(v.AuxInt)] {
					// We don't need marks for bodies that
					// have been completely optimized away.
					// TODO: save marks only for bodies which
					// have a faulting instruction or a call?
					continue
				}
				live[v.ID] = true
				q = append(q, v)
				if v.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, v)
				}
			}
		}
	}

// Compute transitive closure of live values.
	for len(q) > 0 {
		// pop a reachable value
		v := q[len(q)-1]
		q = q[:len(q)-1]
		for i, x := range v.Args {
			if v.Op == OpPhi && !reachable[v.Block.Preds[i].b.ID] {
				continue
			}
			if !live[x.ID] {
				live[x.ID] = true
				q = append(q, x) // push
				if x.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, x)
				}
			}
		}
	}

return
}

// deadcode removes dead code from f.
func deadcode(f *Func) {
	// deadcode after regalloc is forbidden for now. Regalloc
	// doesn't quite generate legal SSA which will lead to some
	// required moves being eliminated. See the comment at the
	// top of regalloc.go for details.
	if f.RegAlloc != nil {
		f.Fatalf("deadcode after regalloc")
	}

// Find reachable blocks.
	reachable := ReachableBlocks(f)

// Get rid of edges from dead to live code.
	for _, b := range f.Blocks {
		if reachable[b.ID] {
			continue
		}
		for i := 0; i < len(b.Succs); {
			e := b.Succs[i]
			if reachable[e.b.ID] {
				b.removeEdge(i)
			} else {
				i++
			}
		}
	}

// Get rid of dead edges from live code.
	for _, b := range f.Blocks {
		if !reachable[b.ID] {
			continue
		}
		if b.Kind != BlockFirst {
			continue
		}
		b.removeEdge(1)
		b.Kind = BlockPlain
		b.Likely = BranchUnknown
	}

// Splice out any copies introduced during dead block removal.
	copyelim(f)

// Find live values.
	live, order := liveValues(f, reachable)
	defer f.retDeadcodeLive(live)
	defer f.retDeadcodeLiveOrderStmts(order)

// Remove dead & duplicate entries from namedValues map.
	s := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(s)
	i := 0
	for _, name := range f.Names {
		j := 0
		s.clear()
		values := f.NamedValues[name]
		for _, v := range values {
			if live[v.ID] && !s.contains(v.ID) {
				values[j] = v
				j++
				s.add(v.ID)
			}
		}
		if j == 0 {
			delete(f.NamedValues, name)
		} else {
			f.Names[i] = name
			i++
			for k := len(values) - 1; k >= j; k-- {
				values[k] = nil
			}
			f.NamedValues[name] = values[:j]
		}
	}
	for k := len(f.Names) - 1; k >= i; k-- {
		f.Names[k] = LocalSlot{}
	}
	f.Names = f.Names[:i]

pendingLines := f.cachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
	pendingLines.clear()

// Unlink values and conserve statement boundaries
	for i, b := range f.Blocks {
		if !reachable[b.ID] {
			// TODO what if control is statement boundary? Too late here.
			b.ResetControls()
		}
		for _, v := range b.Values {
			if !live[v.ID] {
				v.resetArgs()
				if v.Pos.IsStmt() == src.PosIsStmt && reachable[b.ID] {
					pendingLines.set(v.Pos, int32(i)) // TODO could be more than one pos for a line
				}
			}
		}
	}

// Find new homes for lost lines -- require earliest in data flow with same line that is also in same block
	for i := len(order) - 1; i >= 0; i-- {
		w := order[i]
		if j := pendingLines.get(w.Pos); j > -1 && f.Blocks[j] == w.Block {
			w.Pos = w.Pos.WithIsStmt()
			pendingLines.remove(w.Pos)
		}
	}

// Any boundary that failed to match a live value can move to a block end
	pendingLines.foreachEntry(func(j int32, l uint, bi int32) {
		b := f.Blocks[bi]
		if b.Pos.Line() == l && b.Pos.FileIndex() == j {
			b.Pos = b.Pos.WithIsStmt()
		}
	})

// Remove dead values from blocks' value list. Return dead
	// values to the allocator.
	for _, b := range f.Blocks {
		i := 0
		for _, v := range b.Values {
			if live[v.ID] {
				b.Values[i] = v
				i++
			} else {
				f.freeValue(v)
			}
		}
		// aid GC
		tail := b.Values[i:]
		for j := range tail {
			tail[j] = nil
		}
		b.Values = b.Values[:i]
	}

// Remove dead blocks from WBLoads list.
	i = 0
	for _, b := range f.WBLoads {
		if reachable[b.ID] {
			f.WBLoads[i] = b
			i++
		}
	}
	for j := i; j < len(f.WBLoads); j++ {
		f.WBLoads[j] = nil
	}
	f.WBLoads = f.WBLoads[:i]

// Remove unreachable blocks. Return dead blocks to allocator.
	i = 0
	for _, b := range f.Blocks {
		if reachable[b.ID] {
			f.Blocks[i] = b
			i++
		} else {
			if len(b.Values) > 0 {
				b.Fatalf("live values in unreachable block %v: %v", b, b.Values)
			}
			f.freeBlock(b)
		}
	}
	// zero remainder to help GC
	tail := f.Blocks[i:]
	for j := range tail {
		tail[j] = nil
	}
	f.Blocks = f.Blocks[:i]
}

// removeEdge removes the i'th outgoing edge from b (and
// the corresponding incoming edge from b.Succs[i].b).
func (b *Block) removeEdge(i int) {
	e := b.Succs[i]
	c := e.b
	j := e.i

// Adjust b.Succs
	b.removeSucc(i)

// Adjust c.Preds
	c.removePred(j)

// Remove phi args from c's phis.
	n := len(c.Preds)
	for _, v := range c.Values {
		if v.Op != OpPhi {
			continue
		}
		v.Args[j].Uses--
		v.Args[j] = v.Args[n]
		v.Args[n] = nil
		v.Args = v.Args[:n]
		phielimValue(v)
		// Note: this is trickier than it looks. Replacing
		// a Phi with a Copy can in general cause problems because
		// Phi and Copy don't have exactly the same semantics.
		// Phi arguments always come from a predecessor block,
		// whereas copies don't. This matters in loops like:
		// 1: x = (Phi y)
		//    y = (Add x 1)
		//    goto 1
		// If we replace Phi->Copy, we get
		// 1: x = (Copy y)
		//    y = (Add x 1)
		//    goto 1
		// (Phi y) refers to the *previous* value of y, whereas
		// (Copy y) refers to the *current* value of y.
		// The modified code has a cycle and the scheduler
		// will barf on it.
		//
		// Fortunately, this situation can only happen for dead
		// code loops. We know the code we're working with is
		// not dead, so we're ok.
		// Proof: If we have a potential bad cycle, we have a
		// situation like this:
		//   x = (Phi z)
		//   y = (op1 x ...)
		//   z = (op2 y ...)
		// Where opX are not Phi ops. But such a situation
		// implies a cycle in the dominator graph. In the
		// example, x.Block dominates y.Block, y.Block dominates
		// z.Block, and z.Block dominates x.Block (treating
		// "dominates" as reflexive).  Cycles in the dominator
		// graph can only happen in an unreachable cycle.
	}
}

${this.title}

Code Editor : deadcode.go