Source file src/pkg/cmd/compile/internal/ssa/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					n := len(b.Preds)
    95					phi.Args[i].Uses--
    96					phi.Args[i] = phi.Args[n]
    97					phi.Args[n] = nil
    98					phi.Args = phi.Args[:n]
    99					// splitting occasionally leads to a phi having
   100					// a single argument (occurs with -N)
   101					if n == 1 {
   102						phi.Op = OpCopy
   103					}
   104					// Don't increment i in this case because we moved
   105					// an unprocessed predecessor down into slot i.
   106				} else {
   107					// splice it in
   108					p.Succs[pi] = Edge{d, 0}
   109					b.Preds[i] = Edge{d, 0}
   110					d.Preds = append(d.Preds, Edge{p, pi})
   111					d.Succs = append(d.Succs, Edge{b, i})
   112					i++
   113				}
   114			}
   115		}
   116	}
   117	

View as plain text