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 ssacompile
     6  
     7  import (
     8  	"cmd/compile/internal/ssa"
     9  	"cmd/compile/internal/ssa/block"
    10  	"cmd/internal/src"
    11  )
    12  
    13  // deadcode removes dead code from f.
    14  func deadcode(f *ssa.Func) {
    15  	// deadcode after regalloc is forbidden for now. Regalloc
    16  	// doesn't quite generate legal SSA which will lead to some
    17  	// required moves being eliminated. See the comment at the
    18  	// top of regalloc.go for details.
    19  	// TODO: regalloc now generates strict SSA, figure out
    20  	// what subset of the deadcode pass we can run.
    21  	if f.RegAlloc != nil {
    22  		f.Fatalf("deadcode after regalloc")
    23  	}
    24  
    25  	// Find reachable blocks.
    26  	reachable := ssa.ReachableBlocks(f)
    27  
    28  	// Get rid of edges from dead to live code.
    29  	for _, b := range f.Blocks {
    30  		if reachable[b.ID] {
    31  			continue
    32  		}
    33  		for i := 0; i < len(b.Succs); {
    34  			e := b.Succs[i]
    35  			if reachable[e.B.ID] {
    36  				b.RemoveEdge(i)
    37  			} else {
    38  				i++
    39  			}
    40  		}
    41  	}
    42  
    43  	// Get rid of dead edges from live code.
    44  	for _, b := range f.Blocks {
    45  		if !reachable[b.ID] {
    46  			continue
    47  		}
    48  		if b.Kind != block.BlockFirst {
    49  			continue
    50  		}
    51  		b.RemoveEdge(1)
    52  		b.Kind = block.BlockPlain
    53  		b.Likely = ssa.BranchUnknown
    54  	}
    55  
    56  	// Splice out any copies introduced during dead block removal.
    57  	copyelim(f)
    58  
    59  	// Find live values.
    60  	live, order := ssa.LiveValues(f, reachable)
    61  	defer func() { f.Cache.FreeBoolSlice(live) }()
    62  	defer func() { f.Cache.FreeValueSlice(order) }()
    63  
    64  	// Remove dead & duplicate entries from namedValues map.
    65  	s := f.NewSparseSet(f.NumValues())
    66  	defer f.RetSparseSet(s)
    67  	i := 0
    68  	for _, name := range f.Names {
    69  		j := 0
    70  		s.Clear()
    71  		values := f.NamedValues[name]
    72  		for _, v := range values {
    73  			if live[v.ID] && !s.Contains(v.ID) {
    74  				values[j] = v
    75  				j++
    76  				s.Add(v.ID)
    77  			}
    78  		}
    79  		if j == 0 {
    80  			delete(f.NamedValues, name)
    81  		} else {
    82  			f.Names[i] = name
    83  			i++
    84  			for k := len(values) - 1; k >= j; k-- {
    85  				values[k] = nil
    86  			}
    87  			f.NamedValues[name] = values[:j]
    88  		}
    89  	}
    90  	clear(f.Names[i:])
    91  	f.Names = f.Names[:i]
    92  
    93  	pendingLines := f.CachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
    94  	pendingLines.Clear()
    95  
    96  	// Unlink values and conserve statement boundaries
    97  	for i, b := range f.Blocks {
    98  		if !reachable[b.ID] {
    99  			// TODO what if control is statement boundary? Too late here.
   100  			b.ResetControls()
   101  		}
   102  		for _, v := range b.Values {
   103  			if !live[v.ID] {
   104  				v.ResetArgs()
   105  				if v.Pos.IsStmt() == src.PosIsStmt && reachable[b.ID] {
   106  					pendingLines.Set(v.Pos, int32(i)) // TODO could be more than one pos for a line
   107  				}
   108  			}
   109  		}
   110  	}
   111  
   112  	// Find new homes for lost lines -- require earliest in data flow with same line that is also in same block
   113  	for i := len(order) - 1; i >= 0; i-- {
   114  		w := order[i]
   115  		if j, ok := pendingLines.Get(w.Pos); ok && f.Blocks[j] == w.Block {
   116  			w.Pos = w.Pos.WithIsStmt()
   117  			pendingLines.Remove(w.Pos)
   118  		}
   119  	}
   120  
   121  	// Any boundary that failed to match a live value can move to a block end
   122  	pendingLines.ForeachEntry(func(j int32, l uint, bi int32) {
   123  		b := f.Blocks[bi]
   124  		if b.Pos.Line() == l && b.Pos.FileIndex() == j {
   125  			b.Pos = b.Pos.WithIsStmt()
   126  		}
   127  	})
   128  
   129  	// Remove dead values from blocks' value list. Return dead
   130  	// values to the allocator.
   131  	for _, b := range f.Blocks {
   132  		i := 0
   133  		for _, v := range b.Values {
   134  			if live[v.ID] {
   135  				b.Values[i] = v
   136  				i++
   137  			} else {
   138  				f.FreeValue(v)
   139  			}
   140  		}
   141  		b.TruncateValues(i)
   142  	}
   143  
   144  	// Remove unreachable blocks. Return dead blocks to allocator.
   145  	i = 0
   146  	for _, b := range f.Blocks {
   147  		if reachable[b.ID] {
   148  			f.Blocks[i] = b
   149  			i++
   150  		} else {
   151  			if len(b.Values) > 0 {
   152  				b.Fatalf("live values in unreachable block %v: %v", b, b.Values)
   153  			}
   154  			f.FreeBlock(b)
   155  		}
   156  	}
   157  	// zero remainder to help GC
   158  	clear(f.Blocks[i:])
   159  	f.Blocks = f.Blocks[:i]
   160  }
   161
View as plain text