critical.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 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
View as plain text