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  					// CPU features are execution-invariant facts: d
    72  					// executes only after p and unconditionally jumps
    73  					// to b, so both blocks' features hold in d.
    74  					d.CPUfeatures = p.CPUfeatures | b.CPUfeatures
    75  					blocks[argID] = d
    76  					if f.Pass.Debug > 0 {
    77  						f.Warnl(p.Pos, "split critical edge")
    78  						if d.CPUfeatures != ssa.CPUNone {
    79  							f.Warnl(p.Pos, "split-edge block b%d has features %v", d.ID, d.CPUfeatures)
    80  						}
    81  					}
    82  				} else {
    83  					reusedBlock = true
    84  					// d gains another predecessor, so only the
    85  					// features common to all of its predecessors
    86  					// (plus b's) are still guaranteed.
    87  					d.CPUfeatures &= p.CPUfeatures | b.CPUfeatures
    88  					if f.Pass.Debug > 0 && d.CPUfeatures != ssa.CPUNone {
    89  						f.Warnl(p.Pos, "reused split-edge block b%d has features %v", d.ID, d.CPUfeatures)
    90  					}
    91  				}
    92  			} else {
    93  				// no existing block, so allocate a new block
    94  				// to place on the edge
    95  				d = f.NewBlock(block.BlockPlain)
    96  				d.Pos = p.Pos
    97  				// See above for why d inherits these features.
    98  				d.CPUfeatures = p.CPUfeatures | b.CPUfeatures
    99  				if f.Pass.Debug > 0 {
   100  					f.Warnl(p.Pos, "split critical edge")
   101  					if d.CPUfeatures != ssa.CPUNone {
   102  						f.Warnl(p.Pos, "split-edge block b%d has features %v", d.ID, d.CPUfeatures)
   103  					}
   104  				}
   105  			}
   106  
   107  			// if this not the first argument for the
   108  			// block, then we need to remove the
   109  			// corresponding elements from the block
   110  			// predecessors and phi args
   111  			if reusedBlock {
   112  				// Add p->d edge
   113  				p.Succs[pi] = ssa.Edge{B: d, I: len(d.Preds)}
   114  				d.Preds = append(d.Preds, ssa.Edge{B: p, I: pi})
   115  
   116  				// Remove p as a predecessor from b.
   117  				b.RemovePred(i)
   118  
   119  				// Update corresponding phi args
   120  				b.RemovePhiArg(phi, i)
   121  
   122  				// splitting occasionally leads to a phi having
   123  				// a single argument (occurs with -N)
   124  				// Don't increment i in this case because we moved
   125  				// an unprocessed predecessor down into slot i.
   126  			} else {
   127  				// splice it in
   128  				p.Succs[pi] = ssa.Edge{B: d, I: 0}
   129  				b.Preds[i] = ssa.Edge{B: d, I: 0}
   130  				d.Preds = append(d.Preds, ssa.Edge{B: p, I: pi})
   131  				d.Succs = append(d.Succs, ssa.Edge{B: b, I: i})
   132  				i++
   133  			}
   134  		}
   135  	}
   136  }
   137
View as plain text