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