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 := 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  				b.removePhiArg(phi, i)
    95  
    96  				// splitting occasionally leads to a phi having
    97  				// a single argument (occurs with -N)
    98  				// TODO(cuonglm,khr): replace this with phielimValue, and
    99  				//                    make removePhiArg incorporates that.
   100  				if len(b.Preds) == 1 {
   101  					phi.Op = OpCopy
   102  				}
   103  				// Don't increment i in this case because we moved
   104  				// an unprocessed predecessor down into slot i.
   105  			} else {
   106  				// splice it in
   107  				p.Succs[pi] = Edge{d, 0}
   108  				b.Preds[i] = Edge{d, 0}
   109  				d.Preds = append(d.Preds, Edge{p, pi})
   110  				d.Succs = append(d.Succs, Edge{b, i})
   111  				i++
   112  			}
   113  		}
   114  	}
   115  }
   116
View as plain text