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