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 // Since s did not have a Phi op corresponding to 52 // the phi op in b, the other edges coming into s 53 // must be loopback edges from s, so v is the right 54 // argument to v! 55 args := make([]*Value, len(v.Args)) 56 copy(args, v.Args) 57 v.resetArgs() 58 for x := 0; x < j; x++ { 59 v.AddArg(v) 60 } 61 v.AddArg(args[0]) 62 for x := j + 1; x < ns; x++ { 63 v.AddArg(v) 64 } 65 for _, a := range args[1:] { 66 v.AddArg(a) 67 } 68 } 69 b.Values[k] = v 70 k++ 71 } 72 b.Values = b.Values[:k] 73 } 74 75 // Merge the blocks' values. 76 for _, v := range b.Values { 77 v.Block = s 78 } 79 k := len(b.Values) 80 m := len(s.Values) 81 for i := 0; i < k; i++ { 82 s.Values = append(s.Values, nil) 83 } 84 copy(s.Values[k:], s.Values[:m]) 85 copy(s.Values, b.Values) 86 } 87 if n < len(f.Blocks) { 88 f.invalidateCFG() 89 tail := f.Blocks[n:] 90 for i := range tail { 91 tail[i] = nil 92 } 93 f.Blocks = f.Blocks[:n] 94 } 95 } 96 97 // emptyBlock returns true if the block does not contain actual 98 // instructions 99 func emptyBlock(b *Block) bool { 100 for _, v := range b.Values { 101 if v.Op != OpPhi { 102 return false 103 } 104 } 105 return true 106 } 107 108 // trimmableBlock returns true if the block can be trimmed from the CFG, 109 // subject to the following criteria: 110 // - it should not be the first block 111 // - it should be BlockPlain 112 // - it should not loop back to itself 113 // - it either is the single predecessor of the successor block or 114 // contains no actual instructions 115 func trimmableBlock(b *Block) bool { 116 if b.Kind != BlockPlain || b == b.Func.Entry { 117 return false 118 } 119 s := b.Succs[0].b 120 return s != b && (len(s.Preds) == 1 || emptyBlock(b)) 121 } 122 123 // mergePhi adjusts the number of `v`s arguments to account for merge 124 // of `b`, which was `i`th predecessor of the `v`s block. 125 func mergePhi(v *Value, i int, b *Block) { 126 u := v.Args[i] 127 if u.Block == b { 128 if u.Op != OpPhi { 129 b.Func.Fatalf("value %s is not a phi operation", u.LongString()) 130 } 131 // If the original block contained u = (u0, u1, ..., un) and 132 // the current phi is 133 // v = (v0, v1, ..., u, ..., vk) 134 // then the merged phi is 135 // v = (v0, v1, ..., u0, ..., vk, u1, ..., un) 136 v.SetArg(i, u.Args[0]) 137 v.AddArgs(u.Args[1:]...) 138 } else { 139 // If the original block contained u = (u0, u1, ..., un) and 140 // the current phi is 141 // v = (v0, v1, ..., vi, ..., vk) 142 // i.e. it does not use a value from the predecessor block, 143 // then the merged phi is 144 // v = (v0, v1, ..., vk, vi, vi, ...) 145 for j := 1; j < len(b.Preds); j++ { 146 v.AddArg(v.Args[i]) 147 } 148 } 149 } 150
