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