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