1 // Copyright 2016 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 // trim removes blocks with no code in them. 8 // These blocks were inserted to remove critical edges. 9 func trim(f *Func) { 10 n := 0 11 for _, b := range f.Blocks { 12 if !trimmableBlock(b) { 13 f.Blocks[n] = b 14 n++ 15 continue 16 } 17 18 // Splice b out of the graph. NOTE: `mergePhi` depends on the 19 // order, in which the predecessors edges are merged here. 20 p, i := b.Preds[0].b, b.Preds[0].i 21 s, j := b.Succs[0].b, b.Succs[0].i 22 ns := len(s.Preds) 23 p.Succs[i] = Edge{s, j} 24 s.Preds[j] = Edge{p, i} 25 26 for _, e := range b.Preds[1:] { 27 p, i := e.b, e.i 28 p.Succs[i] = Edge{s, len(s.Preds)} 29 s.Preds = append(s.Preds, Edge{p, i}) 30 } 31 32 // If `s` had more than one predecessor, update its phi-ops to 33 // account for the merge. 34 if ns > 1 { 35 for _, v := range s.Values { 36 if v.Op == OpPhi { 37 mergePhi(v, j, b) 38 } 39 } 40 // Remove the phi-ops from `b` if they were merged into the 41 // phi-ops of `s`. 42 k := 0 43 for _, v := range b.Values { 44 if v.Op == OpPhi { 45 if v.Uses == 0 { 46 v.resetArgs() 47 continue 48 } 49 // Pad the arguments of the remaining phi-ops, so 50 // they match the new predecessor count of `s`. 51 for len(v.Args) < len(s.Preds) { 52 v.AddArg(v.Args[0]) 53 } 54 } 55 b.Values[k] = v 56 k++ 57 } 58 b.Values = b.Values[:k] 59 } 60 61 // Merge the blocks' values. 62 for _, v := range b.Values { 63 v.Block = s 64 } 65 k := len(b.Values) 66 m := len(s.Values) 67 for i := 0; i < k; i++ { 68 s.Values = append(s.Values, nil) 69 } 70 copy(s.Values[k:], s.Values[:m]) 71 copy(s.Values, b.Values) 72 } 73 if n < len(f.Blocks) { 74 f.invalidateCFG() 75 tail := f.Blocks[n:] 76 for i := range tail { 77 tail[i] = nil 78 } 79 f.Blocks = f.Blocks[:n] 80 } 81 } 82 83 // emptyBlock returns true if the block does not contain actual 84 // instructions 85 func emptyBlock(b *Block) bool { 86 for _, v := range b.Values { 87 if v.Op != OpPhi { 88 return false 89 } 90 } 91 return true 92 } 93 94 // trimmableBlock returns true if the block can be trimmed from the CFG, 95 // subject to the following criteria: 96 // - it should not be the first block 97 // - it should be BlockPlain 98 // - it should not loop back to itself 99 // - it either is the single predecessor of the successor block or 100 // contains no actual instructions 101 func trimmableBlock(b *Block) bool { 102 if b.Kind != BlockPlain || b == b.Func.Entry { 103 return false 104 } 105 s := b.Succs[0].b 106 return s != b && (len(s.Preds) == 1 || emptyBlock(b)) 107 } 108 109 // mergePhi adjusts the number of `v`s arguments to account for merge 110 // of `b`, which was `i`th predecessor of the `v`s block. Returns 111 // `v`. 112 func mergePhi(v *Value, i int, b *Block) *Value { 113 u := v.Args[i] 114 if u.Block == b { 115 if u.Op != OpPhi { 116 b.Func.Fatalf("value %s is not a phi operation", u.LongString()) 117 } 118 // If the original block contained u = (u0, u1, ..., un) and 119 // the current phi is 120 // v = (v0, v1, ..., u, ..., vk) 121 // then the merged phi is 122 // v = (v0, v1, ..., u0, ..., vk, u1, ..., un) 123 v.SetArg(i, u.Args[0]) 124 v.AddArgs(u.Args[1:]...) 125 } else { 126 // If the original block contained u = (u0, u1, ..., un) and 127 // the current phi is 128 // v = (v0, v1, ..., vi, ..., vk) 129 // i.e. it does not use a value from the predecessor block, 130 // then the merged phi is 131 // v = (v0, v1, ..., vk, vi, vi, ...) 132 for j := 1; j < len(b.Preds); j++ { 133 v.AddArg(v.Args[i]) 134 } 135 } 136 return v 137 } 138
