Source file src/cmd/compile/internal/ssa/deadcode.go

Documentation: cmd/compile/internal/ssa

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

View as plain text