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 // critical splits critical edges (those that go from a block with 8 // more than one outedge to a block with more than one inedge). 9 // Regalloc wants a critical-edge-free CFG so it can implement phi values. 10 func critical(f *Func) { 11 // maps from phi arg ID to the new block created for that argument 12 blocks := make([]*Block, f.NumValues()) 13 // need to iterate over f.Blocks without range, as we might 14 // need to split critical edges on newly constructed blocks 15 for j := 0; j < len(f.Blocks); j++ { 16 b := f.Blocks[j] 17 if len(b.Preds) <= 1 { 18 continue 19 } 20 21 var phi *Value 22 // determine if we've only got a single phi in this 23 // block, this is easier to handle than the general 24 // case of a block with multiple phi values. 25 for _, v := range b.Values { 26 if v.Op == OpPhi { 27 if phi != nil { 28 phi = nil 29 break 30 } 31 phi = v 32 } 33 } 34 35 // reset our block map 36 if phi != nil { 37 for _, v := range phi.Args { 38 blocks[v.ID] = nil 39 } 40 } 41 42 // split input edges coming from multi-output blocks. 43 for i := 0; i < len(b.Preds); { 44 e := b.Preds[i] 45 p := e.b 46 pi := e.i 47 if p.Kind == BlockPlain { 48 i++ 49 continue // only single output block 50 } 51 52 var d *Block // new block used to remove critical edge 53 reusedBlock := false // if true, then this is not the first use of this block 54 if phi != nil { 55 argID := phi.Args[i].ID 56 // find or record the block that we used to split 57 // critical edges for this argument 58 if d = blocks[argID]; d == nil { 59 // splitting doesn't necessarily remove the critical edge, 60 // since we're iterating over len(f.Blocks) above, this forces 61 // the new blocks to be re-examined. 62 d = f.NewBlock(BlockPlain) 63 d.Pos = p.Pos 64 blocks[argID] = d 65 if f.pass.debug > 0 { 66 f.Warnl(p.Pos, "split critical edge") 67 } 68 } else { 69 reusedBlock = true 70 } 71 } else { 72 // no existing block, so allocate a new block 73 // to place on the edge 74 d = f.NewBlock(BlockPlain) 75 d.Pos = p.Pos 76 if f.pass.debug > 0 { 77 f.Warnl(p.Pos, "split critical edge") 78 } 79 } 80 81 // if this not the first argument for the 82 // block, then we need to remove the 83 // corresponding elements from the block 84 // predecessors and phi args 85 if reusedBlock { 86 // Add p->d edge 87 p.Succs[pi] = Edge{d, len(d.Preds)} 88 d.Preds = append(d.Preds, Edge{p, pi}) 89 90 // Remove p as a predecessor from b. 91 b.removePred(i) 92 93 // Update corresponding phi args 94 n := len(b.Preds) 95 phi.Args[i].Uses-- 96 phi.Args[i] = phi.Args[n] 97 phi.Args[n] = nil 98 phi.Args = phi.Args[:n] 99 // splitting occasionally leads to a phi having 100 // a single argument (occurs with -N) 101 if n == 1 { 102 phi.Op = OpCopy 103 } 104 // Don't increment i in this case because we moved 105 // an unprocessed predecessor down into slot i. 106 } else { 107 // splice it in 108 p.Succs[pi] = Edge{d, 0} 109 b.Preds[i] = Edge{d, 0} 110 d.Preds = append(d.Preds, Edge{p, pi}) 111 d.Succs = append(d.Succs, Edge{b, i}) 112 i++ 113 } 114 } 115 } 116 } 117
