Source file src/pkg/cmd/compile/internal/ssa/deadcode.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/internal/src"
     9	)
    10	
    11	// findlive returns the reachable blocks and live values in f.
    12	// The caller should call f.retDeadcodeLive(live) when it is done with it.
    13	func findlive(f *Func) (reachable []bool, live []bool) {
    14		reachable = ReachableBlocks(f)
    15		var order []*Value
    16		live, order = liveValues(f, reachable)
    17		f.retDeadcodeLiveOrderStmts(order)
    18		return
    19	}
    20	
    21	// ReachableBlocks returns the reachable blocks in f.
    22	func ReachableBlocks(f *Func) []bool {
    23		reachable := make([]bool, f.NumBlocks())
    24		reachable[f.Entry.ID] = true
    25		p := make([]*Block, 0, 64) // stack-like worklist
    26		p = append(p, f.Entry)
    27		for len(p) > 0 {
    28			// Pop a reachable block
    29			b := p[len(p)-1]
    30			p = p[:len(p)-1]
    31			// Mark successors as reachable
    32			s := b.Succs
    33			if b.Kind == BlockFirst {
    34				s = s[:1]
    35			}
    36			for _, e := range s {
    37				c := e.b
    38				if int(c.ID) >= len(reachable) {
    39					f.Fatalf("block %s >= f.NumBlocks()=%d?", c, len(reachable))
    40				}
    41				if !reachable[c.ID] {
    42					reachable[c.ID] = true
    43					p = append(p, c) // push
    44				}
    45			}
    46		}
    47		return reachable
    48	}
    49	
    50	// liveValues returns the live values in f and a list of values that are eligible
    51	// to be statements in reversed data flow order.
    52	// The second result is used to help conserve statement boundaries for debugging.
    53	// reachable is a map from block ID to whether the block is reachable.
    54	// The caller should call f.retDeadcodeLive(live) and f.retDeadcodeLiveOrderStmts(liveOrderStmts)
    55	// when they are done with the return values.
    56	func liveValues(f *Func, reachable []bool) (live []bool, liveOrderStmts []*Value) {
    57		live = f.newDeadcodeLive()
    58		if cap(live) < f.NumValues() {
    59			live = make([]bool, f.NumValues())
    60		} else {
    61			live = live[:f.NumValues()]
    62			for i := range live {
    63				live[i] = false
    64			}
    65		}
    66	
    67		liveOrderStmts = f.newDeadcodeLiveOrderStmts()
    68		liveOrderStmts = liveOrderStmts[:0]
    69	
    70		// After regalloc, consider all values to be live.
    71		// See the comment at the top of regalloc.go and in deadcode for details.
    72		if f.RegAlloc != nil {
    73			for i := range live {
    74				live[i] = true
    75			}
    76			return
    77		}
    78	
    79		// Record all the inline indexes we need
    80		var liveInlIdx map[int]bool
    81		pt := f.Config.ctxt.PosTable
    82		for _, b := range f.Blocks {
    83			for _, v := range b.Values {
    84				i := pt.Pos(v.Pos).Base().InliningIndex()
    85				if i < 0 {
    86					continue
    87				}
    88				if liveInlIdx == nil {
    89					liveInlIdx = map[int]bool{}
    90				}
    91				liveInlIdx[i] = true
    92			}
    93			i := pt.Pos(b.Pos).Base().InliningIndex()
    94			if i < 0 {
    95				continue
    96			}
    97			if liveInlIdx == nil {
    98				liveInlIdx = map[int]bool{}
    99			}
   100			liveInlIdx[i] = true
   101		}
   102	
   103		// Find all live values
   104		q := f.Cache.deadcode.q[:0]
   105		defer func() { f.Cache.deadcode.q = q }()
   106	
   107		// Starting set: all control values of reachable blocks are live.
   108		// Calls are live (because callee can observe the memory state).
   109		for _, b := range f.Blocks {
   110			if !reachable[b.ID] {
   111				continue
   112			}
   113			if v := b.Control; v != nil && !live[v.ID] {
   114				live[v.ID] = true
   115				q = append(q, v)
   116				if v.Pos.IsStmt() != src.PosNotStmt {
   117					liveOrderStmts = append(liveOrderStmts, v)
   118				}
   119			}
   120			for _, v := range b.Values {
   121				if (opcodeTable[v.Op].call || opcodeTable[v.Op].hasSideEffects) && !live[v.ID] {
   122					live[v.ID] = true
   123					q = append(q, v)
   124					if v.Pos.IsStmt() != src.PosNotStmt {
   125						liveOrderStmts = append(liveOrderStmts, v)
   126					}
   127				}
   128				if v.Type.IsVoid() && !live[v.ID] {
   129					// The only Void ops are nil checks and inline marks.  We must keep these.
   130					if v.Op == OpInlMark && !liveInlIdx[int(v.AuxInt)] {
   131						// We don't need marks for bodies that
   132						// have been completely optimized away.
   133						// TODO: save marks only for bodies which
   134						// have a faulting instruction or a call?
   135						continue
   136					}
   137					live[v.ID] = true
   138					q = append(q, v)
   139					if v.Pos.IsStmt() != src.PosNotStmt {
   140						liveOrderStmts = append(liveOrderStmts, v)
   141					}
   142				}
   143			}
   144		}
   145	
   146		// Compute transitive closure of live values.
   147		for len(q) > 0 {
   148			// pop a reachable value
   149			v := q[len(q)-1]
   150			q = q[:len(q)-1]
   151			for i, x := range v.Args {
   152				if v.Op == OpPhi && !reachable[v.Block.Preds[i].b.ID] {
   153					continue
   154				}
   155				if !live[x.ID] {
   156					live[x.ID] = true
   157					q = append(q, x) // push
   158					if x.Pos.IsStmt() != src.PosNotStmt {
   159						liveOrderStmts = append(liveOrderStmts, x)
   160					}
   161				}
   162			}
   163		}
   164	
   165		return
   166	}
   167	
   168	// deadcode removes dead code from f.
   169	func deadcode(f *Func) {
   170		// deadcode after regalloc is forbidden for now. Regalloc
   171		// doesn't quite generate legal SSA which will lead to some
   172		// required moves being eliminated. See the comment at the
   173		// top of regalloc.go for details.
   174		if f.RegAlloc != nil {
   175			f.Fatalf("deadcode after regalloc")
   176		}
   177	
   178		// Find reachable blocks.
   179		reachable := ReachableBlocks(f)
   180	
   181		// Get rid of edges from dead to live code.
   182		for _, b := range f.Blocks {
   183			if reachable[b.ID] {
   184				continue
   185			}
   186			for i := 0; i < len(b.Succs); {
   187				e := b.Succs[i]
   188				if reachable[e.b.ID] {
   189					b.removeEdge(i)
   190				} else {
   191					i++
   192				}
   193			}
   194		}
   195	
   196		// Get rid of dead edges from live code.
   197		for _, b := range f.Blocks {
   198			if !reachable[b.ID] {
   199				continue
   200			}
   201			if b.Kind != BlockFirst {
   202				continue
   203			}
   204			b.removeEdge(1)
   205			b.Kind = BlockPlain
   206			b.Likely = BranchUnknown
   207		}
   208	
   209		// Splice out any copies introduced during dead block removal.
   210		copyelim(f)
   211	
   212		// Find live values.
   213		live, order := liveValues(f, reachable)
   214		defer f.retDeadcodeLive(live)
   215		defer f.retDeadcodeLiveOrderStmts(order)
   216	
   217		// Remove dead & duplicate entries from namedValues map.
   218		s := f.newSparseSet(f.NumValues())
   219		defer f.retSparseSet(s)
   220		i := 0
   221		for _, name := range f.Names {
   222			j := 0
   223			s.clear()
   224			values := f.NamedValues[name]
   225			for _, v := range values {
   226				if live[v.ID] && !s.contains(v.ID) {
   227					values[j] = v
   228					j++
   229					s.add(v.ID)
   230				}
   231			}
   232			if j == 0 {
   233				delete(f.NamedValues, name)
   234			} else {
   235				f.Names[i] = name
   236				i++
   237				for k := len(values) - 1; k >= j; k-- {
   238					values[k] = nil
   239				}
   240				f.NamedValues[name] = values[:j]
   241			}
   242		}
   243		for k := len(f.Names) - 1; k >= i; k-- {
   244			f.Names[k] = LocalSlot{}
   245		}
   246		f.Names = f.Names[:i]
   247	
   248		pendingLines := f.cachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
   249		pendingLines.clear()
   250	
   251		// Unlink values and conserve statement boundaries
   252		for i, b := range f.Blocks {
   253			if !reachable[b.ID] {
   254				// TODO what if control is statement boundary? Too late here.
   255				b.SetControl(nil)
   256			}
   257			for _, v := range b.Values {
   258				if !live[v.ID] {
   259					v.resetArgs()
   260					if v.Pos.IsStmt() == src.PosIsStmt && reachable[b.ID] {
   261						pendingLines.set(v.Pos, int32(i)) // TODO could be more than one pos for a line
   262					}
   263				}
   264			}
   265		}
   266	
   267		// Find new homes for lost lines -- require earliest in data flow with same line that is also in same block
   268		for i := len(order) - 1; i >= 0; i-- {
   269			w := order[i]
   270			if j := pendingLines.get(w.Pos); j > -1 && f.Blocks[j] == w.Block {
   271				w.Pos = w.Pos.WithIsStmt()
   272				pendingLines.remove(w.Pos)
   273			}
   274		}
   275	
   276		// Any boundary that failed to match a live value can move to a block end
   277		pendingLines.foreachEntry(func(j int32, l uint, bi int32) {
   278			b := f.Blocks[bi]
   279			if b.Pos.Line() == l && b.Pos.FileIndex() == j {
   280				b.Pos = b.Pos.WithIsStmt()
   281			}
   282		})
   283	
   284		// Remove dead values from blocks' value list. Return dead
   285		// values to the allocator.
   286		for _, b := range f.Blocks {
   287			i := 0
   288			for _, v := range b.Values {
   289				if live[v.ID] {
   290					b.Values[i] = v
   291					i++
   292				} else {
   293					f.freeValue(v)
   294				}
   295			}
   296			// aid GC
   297			tail := b.Values[i:]
   298			for j := range tail {
   299				tail[j] = nil
   300			}
   301			b.Values = b.Values[:i]
   302		}
   303	
   304		// Remove dead blocks from WBLoads list.
   305		i = 0
   306		for _, b := range f.WBLoads {
   307			if reachable[b.ID] {
   308				f.WBLoads[i] = b
   309				i++
   310			}
   311		}
   312		for j := i; j < len(f.WBLoads); j++ {
   313			f.WBLoads[j] = nil
   314		}
   315		f.WBLoads = f.WBLoads[:i]
   316	
   317		// Remove unreachable blocks. Return dead blocks to allocator.
   318		i = 0
   319		for _, b := range f.Blocks {
   320			if reachable[b.ID] {
   321				f.Blocks[i] = b
   322				i++
   323			} else {
   324				if len(b.Values) > 0 {
   325					b.Fatalf("live values in unreachable block %v: %v", b, b.Values)
   326				}
   327				f.freeBlock(b)
   328			}
   329		}
   330		// zero remainder to help GC
   331		tail := f.Blocks[i:]
   332		for j := range tail {
   333			tail[j] = nil
   334		}
   335		f.Blocks = f.Blocks[:i]
   336	}
   337	
   338	// removeEdge removes the i'th outgoing edge from b (and
   339	// the corresponding incoming edge from b.Succs[i].b).
   340	func (b *Block) removeEdge(i int) {
   341		e := b.Succs[i]
   342		c := e.b
   343		j := e.i
   344	
   345		// Adjust b.Succs
   346		b.removeSucc(i)
   347	
   348		// Adjust c.Preds
   349		c.removePred(j)
   350	
   351		// Remove phi args from c's phis.
   352		n := len(c.Preds)
   353		for _, v := range c.Values {
   354			if v.Op != OpPhi {
   355				continue
   356			}
   357			v.Args[j].Uses--
   358			v.Args[j] = v.Args[n]
   359			v.Args[n] = nil
   360			v.Args = v.Args[:n]
   361			phielimValue(v)
   362			// Note: this is trickier than it looks. Replacing
   363			// a Phi with a Copy can in general cause problems because
   364			// Phi and Copy don't have exactly the same semantics.
   365			// Phi arguments always come from a predecessor block,
   366			// whereas copies don't. This matters in loops like:
   367			// 1: x = (Phi y)
   368			//    y = (Add x 1)
   369			//    goto 1
   370			// If we replace Phi->Copy, we get
   371			// 1: x = (Copy y)
   372			//    y = (Add x 1)
   373			//    goto 1
   374			// (Phi y) refers to the *previous* value of y, whereas
   375			// (Copy y) refers to the *current* value of y.
   376			// The modified code has a cycle and the scheduler
   377			// will barf on it.
   378			//
   379			// Fortunately, this situation can only happen for dead
   380			// code loops. We know the code we're working with is
   381			// not dead, so we're ok.
   382			// Proof: If we have a potential bad cycle, we have a
   383			// situation like this:
   384			//   x = (Phi z)
   385			//   y = (op1 x ...)
   386			//   z = (op2 y ...)
   387			// Where opX are not Phi ops. But such a situation
   388			// implies a cycle in the dominator graph. In the
   389			// example, x.Block dominates y.Block, y.Block dominates
   390			// z.Block, and z.Block dominates x.Block (treating
   391			// "dominates" as reflexive).  Cycles in the dominator
   392			// graph can only happen in an unreachable cycle.
   393		}
   394	}
   395	

View as plain text