Source file src/cmd/compile/internal/ssa/block.go

Documentation: cmd/compile/internal/ssa

     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  import (
     8  	"cmd/internal/src"
     9  	"fmt"
    10  )
    11  
    12  // Block represents a basic block in the control flow graph of a function.
    13  type Block struct {
    14  	// A unique identifier for the block. The system will attempt to allocate
    15  	// these IDs densely, but no guarantees.
    16  	ID ID
    17  
    18  	// Source position for block's control operation
    19  	Pos src.XPos
    20  
    21  	// The kind of block this is.
    22  	Kind BlockKind
    23  
    24  	// Likely direction for branches.
    25  	// If BranchLikely, Succs[0] is the most likely branch taken.
    26  	// If BranchUnlikely, Succs[1] is the most likely branch taken.
    27  	// Ignored if len(Succs) < 2.
    28  	// Fatal if not BranchUnknown and len(Succs) > 2.
    29  	Likely BranchPrediction
    30  
    31  	// After flagalloc, records whether flags are live at the end of the block.
    32  	FlagsLiveAtEnd bool
    33  
    34  	// Subsequent blocks, if any. The number and order depend on the block kind.
    35  	Succs []Edge
    36  
    37  	// Inverse of successors.
    38  	// The order is significant to Phi nodes in the block.
    39  	// TODO: predecessors is a pain to maintain. Can we somehow order phi
    40  	// arguments by block id and have this field computed explicitly when needed?
    41  	Preds []Edge
    42  
    43  	// A value that determines how the block is exited. Its value depends on the kind
    44  	// of the block. For instance, a BlockIf has a boolean control value and BlockExit
    45  	// has a memory control value.
    46  	Control *Value
    47  
    48  	// Auxiliary info for the block. Its value depends on the Kind.
    49  	Aux interface{}
    50  
    51  	// The unordered set of Values that define the operation of this block.
    52  	// The list must include the control value, if any. (TODO: need this last condition?)
    53  	// After the scheduling pass, this list is ordered.
    54  	Values []*Value
    55  
    56  	// The containing function
    57  	Func *Func
    58  
    59  	// Storage for Succs, Preds, and Values
    60  	succstorage [2]Edge
    61  	predstorage [4]Edge
    62  	valstorage  [9]*Value
    63  }
    64  
    65  // Edge represents a CFG edge.
    66  // Example edges for b branching to either c or d.
    67  // (c and d have other predecessors.)
    68  //   b.Succs = [{c,3}, {d,1}]
    69  //   c.Preds = [?, ?, ?, {b,0}]
    70  //   d.Preds = [?, {b,1}, ?]
    71  // These indexes allow us to edit the CFG in constant time.
    72  // In addition, it informs phi ops in degenerate cases like:
    73  // b:
    74  //    if k then c else c
    75  // c:
    76  //    v = Phi(x, y)
    77  // Then the indexes tell you whether x is chosen from
    78  // the if or else branch from b.
    79  //   b.Succs = [{c,0},{c,1}]
    80  //   c.Preds = [{b,0},{b,1}]
    81  // means x is chosen if k is true.
    82  type Edge struct {
    83  	// block edge goes to (in a Succs list) or from (in a Preds list)
    84  	b *Block
    85  	// index of reverse edge.  Invariant:
    86  	//   e := x.Succs[idx]
    87  	//   e.b.Preds[e.i] = Edge{x,idx}
    88  	// and similarly for predecessors.
    89  	i int
    90  }
    91  
    92  func (e Edge) Block() *Block {
    93  	return e.b
    94  }
    95  func (e Edge) Index() int {
    96  	return e.i
    97  }
    98  
    99  //     kind           control    successors
   100  //   ------------------------------------------
   101  //     Exit        return mem                []
   102  //    Plain               nil            [next]
   103  //       If   a boolean Value      [then, else]
   104  //    Defer               mem  [nopanic, panic]  (control opcode should be OpStaticCall to runtime.deferproc)
   105  type BlockKind int8
   106  
   107  // short form print
   108  func (b *Block) String() string {
   109  	return fmt.Sprintf("b%d", b.ID)
   110  }
   111  
   112  // long form print
   113  func (b *Block) LongString() string {
   114  	s := b.Kind.String()
   115  	if b.Aux != nil {
   116  		s += fmt.Sprintf(" %s", b.Aux)
   117  	}
   118  	if b.Control != nil {
   119  		s += fmt.Sprintf(" %s", b.Control)
   120  	}
   121  	if len(b.Succs) > 0 {
   122  		s += " ->"
   123  		for _, c := range b.Succs {
   124  			s += " " + c.b.String()
   125  		}
   126  	}
   127  	switch b.Likely {
   128  	case BranchUnlikely:
   129  		s += " (unlikely)"
   130  	case BranchLikely:
   131  		s += " (likely)"
   132  	}
   133  	return s
   134  }
   135  
   136  func (b *Block) SetControl(v *Value) {
   137  	if w := b.Control; w != nil {
   138  		w.Uses--
   139  	}
   140  	b.Control = v
   141  	if v != nil {
   142  		v.Uses++
   143  	}
   144  }
   145  
   146  // AddEdgeTo adds an edge from block b to block c. Used during building of the
   147  // SSA graph; do not use on an already-completed SSA graph.
   148  func (b *Block) AddEdgeTo(c *Block) {
   149  	i := len(b.Succs)
   150  	j := len(c.Preds)
   151  	b.Succs = append(b.Succs, Edge{c, j})
   152  	c.Preds = append(c.Preds, Edge{b, i})
   153  	b.Func.invalidateCFG()
   154  }
   155  
   156  // removePred removes the ith input edge from b.
   157  // It is the responsibility of the caller to remove
   158  // the corresponding successor edge.
   159  func (b *Block) removePred(i int) {
   160  	n := len(b.Preds) - 1
   161  	if i != n {
   162  		e := b.Preds[n]
   163  		b.Preds[i] = e
   164  		// Update the other end of the edge we moved.
   165  		e.b.Succs[e.i].i = i
   166  	}
   167  	b.Preds[n] = Edge{}
   168  	b.Preds = b.Preds[:n]
   169  	b.Func.invalidateCFG()
   170  }
   171  
   172  // removeSucc removes the ith output edge from b.
   173  // It is the responsibility of the caller to remove
   174  // the corresponding predecessor edge.
   175  func (b *Block) removeSucc(i int) {
   176  	n := len(b.Succs) - 1
   177  	if i != n {
   178  		e := b.Succs[n]
   179  		b.Succs[i] = e
   180  		// Update the other end of the edge we moved.
   181  		e.b.Preds[e.i].i = i
   182  	}
   183  	b.Succs[n] = Edge{}
   184  	b.Succs = b.Succs[:n]
   185  	b.Func.invalidateCFG()
   186  }
   187  
   188  func (b *Block) swapSuccessors() {
   189  	if len(b.Succs) != 2 {
   190  		b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs))
   191  	}
   192  	e0 := b.Succs[0]
   193  	e1 := b.Succs[1]
   194  	b.Succs[0] = e1
   195  	b.Succs[1] = e0
   196  	e0.b.Preds[e0.i].i = 1
   197  	e1.b.Preds[e1.i].i = 0
   198  	b.Likely *= -1
   199  }
   200  
   201  // LackingPos indicates whether b is a block whose position should be inherited
   202  // from its successors.  This is true if all the values within it have unreliable positions
   203  // and if it is "plain", meaning that there is no control flow that is also very likely
   204  // to correspond to a well-understood source position.
   205  func (b *Block) LackingPos() bool {
   206  	// Non-plain predecessors are If or Defer, which both (1) have two successors,
   207  	// which might have different line numbers and (2) correspond to statements
   208  	// in the source code that have positions, so this case ought not occur anyway.
   209  	if b.Kind != BlockPlain {
   210  		return false
   211  	}
   212  	if b.Pos != src.NoXPos {
   213  		return false
   214  	}
   215  	for _, v := range b.Values {
   216  		if v.LackingPos() {
   217  			continue
   218  		}
   219  		return false
   220  	}
   221  	return true
   222  }
   223  
   224  func (b *Block) Logf(msg string, args ...interface{})   { b.Func.Logf(msg, args...) }
   225  func (b *Block) Log() bool                              { return b.Func.Log() }
   226  func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) }
   227  
   228  type BranchPrediction int8
   229  
   230  const (
   231  	BranchUnlikely = BranchPrediction(-1)
   232  	BranchUnknown  = BranchPrediction(0)
   233  	BranchLikely   = BranchPrediction(+1)
   234  )
   235  

View as plain text