block.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  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 list of values that determine how the block is exited. The number
    44  	// and type of control values depends on the Kind of the block. For
    45  	// instance, a BlockIf has a single boolean control value and BlockExit
    46  	// has a single memory control value.
    47  	//
    48  	// The ControlValues() method may be used to get a slice with the non-nil
    49  	// control values that can be ranged over.
    50  	//
    51  	// Controls[1] must be nil if Controls[0] is nil.
    52  	Controls [2]*Value
    53  
    54  	// Auxiliary info for the block. Its value depends on the Kind.
    55  	Aux    Aux
    56  	AuxInt int64
    57  
    58  	// The unordered set of Values that define the operation of this block.
    59  	// After the scheduling pass, this list is ordered.
    60  	Values []*Value
    61  
    62  	// The containing function
    63  	Func *Func
    64  
    65  	// Storage for Succs, Preds and Values.
    66  	succstorage [2]Edge
    67  	predstorage [4]Edge
    68  	valstorage  [9]*Value
    69  }
    70  
    71  // Edge represents a CFG edge.
    72  // Example edges for b branching to either c or d.
    73  // (c and d have other predecessors.)
    74  //   b.Succs = [{c,3}, {d,1}]
    75  //   c.Preds = [?, ?, ?, {b,0}]
    76  //   d.Preds = [?, {b,1}, ?]
    77  // These indexes allow us to edit the CFG in constant time.
    78  // In addition, it informs phi ops in degenerate cases like:
    79  // b:
    80  //    if k then c else c
    81  // c:
    82  //    v = Phi(x, y)
    83  // Then the indexes tell you whether x is chosen from
    84  // the if or else branch from b.
    85  //   b.Succs = [{c,0},{c,1}]
    86  //   c.Preds = [{b,0},{b,1}]
    87  // means x is chosen if k is true.
    88  type Edge struct {
    89  	// block edge goes to (in a Succs list) or from (in a Preds list)
    90  	b *Block
    91  	// index of reverse edge.  Invariant:
    92  	//   e := x.Succs[idx]
    93  	//   e.b.Preds[e.i] = Edge{x,idx}
    94  	// and similarly for predecessors.
    95  	i int
    96  }
    97  
    98  func (e Edge) Block() *Block {
    99  	return e.b
   100  }
   101  func (e Edge) Index() int {
   102  	return e.i
   103  }
   104  func (e Edge) String() string {
   105  	return fmt.Sprintf("{%v,%d}", e.b, e.i)
   106  }
   107  
   108  //     kind          controls        successors
   109  //   ------------------------------------------
   110  //     Exit      [return mem]                []
   111  //    Plain                []            [next]
   112  //       If   [boolean Value]      [then, else]
   113  //    Defer             [mem]  [nopanic, panic]  (control opcode should be OpStaticCall to runtime.deferproc)
   114  type BlockKind int8
   115  
   116  // short form print
   117  func (b *Block) String() string {
   118  	return fmt.Sprintf("b%d", b.ID)
   119  }
   120  
   121  // long form print
   122  func (b *Block) LongString() string {
   123  	s := b.Kind.String()
   124  	if b.Aux != nil {
   125  		s += fmt.Sprintf(" {%s}", b.Aux)
   126  	}
   127  	if t := b.AuxIntString(); t != "" {
   128  		s += fmt.Sprintf(" [%s]", t)
   129  	}
   130  	for _, c := range b.ControlValues() {
   131  		s += fmt.Sprintf(" %s", c)
   132  	}
   133  	if len(b.Succs) > 0 {
   134  		s += " ->"
   135  		for _, c := range b.Succs {
   136  			s += " " + c.b.String()
   137  		}
   138  	}
   139  	switch b.Likely {
   140  	case BranchUnlikely:
   141  		s += " (unlikely)"
   142  	case BranchLikely:
   143  		s += " (likely)"
   144  	}
   145  	return s
   146  }
   147  
   148  // NumControls returns the number of non-nil control values the
   149  // block has.
   150  func (b *Block) NumControls() int {
   151  	if b.Controls[0] == nil {
   152  		return 0
   153  	}
   154  	if b.Controls[1] == nil {
   155  		return 1
   156  	}
   157  	return 2
   158  }
   159  
   160  // ControlValues returns a slice containing the non-nil control
   161  // values of the block. The index of each control value will be
   162  // the same as it is in the Controls property and can be used
   163  // in ReplaceControl calls.
   164  func (b *Block) ControlValues() []*Value {
   165  	if b.Controls[0] == nil {
   166  		return b.Controls[:0]
   167  	}
   168  	if b.Controls[1] == nil {
   169  		return b.Controls[:1]
   170  	}
   171  	return b.Controls[:2]
   172  }
   173  
   174  // SetControl removes all existing control values and then adds
   175  // the control value provided. The number of control values after
   176  // a call to SetControl will always be 1.
   177  func (b *Block) SetControl(v *Value) {
   178  	b.ResetControls()
   179  	b.Controls[0] = v
   180  	v.Uses++
   181  }
   182  
   183  // ResetControls sets the number of controls for the block to 0.
   184  func (b *Block) ResetControls() {
   185  	if b.Controls[0] != nil {
   186  		b.Controls[0].Uses--
   187  	}
   188  	if b.Controls[1] != nil {
   189  		b.Controls[1].Uses--
   190  	}
   191  	b.Controls = [2]*Value{} // reset both controls to nil
   192  }
   193  
   194  // AddControl appends a control value to the existing list of control values.
   195  func (b *Block) AddControl(v *Value) {
   196  	i := b.NumControls()
   197  	b.Controls[i] = v // panics if array is full
   198  	v.Uses++
   199  }
   200  
   201  // ReplaceControl exchanges the existing control value at the index provided
   202  // for the new value. The index must refer to a valid control value.
   203  func (b *Block) ReplaceControl(i int, v *Value) {
   204  	b.Controls[i].Uses--
   205  	b.Controls[i] = v
   206  	v.Uses++
   207  }
   208  
   209  // CopyControls replaces the controls for this block with those from the
   210  // provided block. The provided block is not modified.
   211  func (b *Block) CopyControls(from *Block) {
   212  	if b == from {
   213  		return
   214  	}
   215  	b.ResetControls()
   216  	for _, c := range from.ControlValues() {
   217  		b.AddControl(c)
   218  	}
   219  }
   220  
   221  // Reset sets the block to the provided kind and clears all the blocks control
   222  // and auxiliary values. Other properties of the block, such as its successors,
   223  // predecessors and values are left unmodified.
   224  func (b *Block) Reset(kind BlockKind) {
   225  	b.Kind = kind
   226  	b.ResetControls()
   227  	b.Aux = nil
   228  	b.AuxInt = 0
   229  }
   230  
   231  // resetWithControl resets b and adds control v.
   232  // It is equivalent to b.Reset(kind); b.AddControl(v),
   233  // except that it is one call instead of two and avoids a bounds check.
   234  // It is intended for use by rewrite rules, where this matters.
   235  func (b *Block) resetWithControl(kind BlockKind, v *Value) {
   236  	b.Kind = kind
   237  	b.ResetControls()
   238  	b.Aux = nil
   239  	b.AuxInt = 0
   240  	b.Controls[0] = v
   241  	v.Uses++
   242  }
   243  
   244  // resetWithControl2 resets b and adds controls v and w.
   245  // It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w),
   246  // except that it is one call instead of three and avoids two bounds checks.
   247  // It is intended for use by rewrite rules, where this matters.
   248  func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) {
   249  	b.Kind = kind
   250  	b.ResetControls()
   251  	b.Aux = nil
   252  	b.AuxInt = 0
   253  	b.Controls[0] = v
   254  	b.Controls[1] = w
   255  	v.Uses++
   256  	w.Uses++
   257  }
   258  
   259  // truncateValues truncates b.Values at the ith element, zeroing subsequent elements.
   260  // The values in b.Values after i must already have had their args reset,
   261  // to maintain correct value uses counts.
   262  func (b *Block) truncateValues(i int) {
   263  	tail := b.Values[i:]
   264  	for j := range tail {
   265  		tail[j] = nil
   266  	}
   267  	b.Values = b.Values[:i]
   268  }
   269  
   270  // AddEdgeTo adds an edge from block b to block c. Used during building of the
   271  // SSA graph; do not use on an already-completed SSA graph.
   272  func (b *Block) AddEdgeTo(c *Block) {
   273  	i := len(b.Succs)
   274  	j := len(c.Preds)
   275  	b.Succs = append(b.Succs, Edge{c, j})
   276  	c.Preds = append(c.Preds, Edge{b, i})
   277  	b.Func.invalidateCFG()
   278  }
   279  
   280  // removePred removes the ith input edge from b.
   281  // It is the responsibility of the caller to remove
   282  // the corresponding successor edge, and adjust any
   283  // phi values by calling b.removePhiArg(v, i).
   284  func (b *Block) removePred(i int) {
   285  	n := len(b.Preds) - 1
   286  	if i != n {
   287  		e := b.Preds[n]
   288  		b.Preds[i] = e
   289  		// Update the other end of the edge we moved.
   290  		e.b.Succs[e.i].i = i
   291  	}
   292  	b.Preds[n] = Edge{}
   293  	b.Preds = b.Preds[:n]
   294  	b.Func.invalidateCFG()
   295  }
   296  
   297  // removeSucc removes the ith output edge from b.
   298  // It is the responsibility of the caller to remove
   299  // the corresponding predecessor edge.
   300  func (b *Block) removeSucc(i int) {
   301  	n := len(b.Succs) - 1
   302  	if i != n {
   303  		e := b.Succs[n]
   304  		b.Succs[i] = e
   305  		// Update the other end of the edge we moved.
   306  		e.b.Preds[e.i].i = i
   307  	}
   308  	b.Succs[n] = Edge{}
   309  	b.Succs = b.Succs[:n]
   310  	b.Func.invalidateCFG()
   311  }
   312  
   313  func (b *Block) swapSuccessors() {
   314  	if len(b.Succs) != 2 {
   315  		b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs))
   316  	}
   317  	e0 := b.Succs[0]
   318  	e1 := b.Succs[1]
   319  	b.Succs[0] = e1
   320  	b.Succs[1] = e0
   321  	e0.b.Preds[e0.i].i = 1
   322  	e1.b.Preds[e1.i].i = 0
   323  	b.Likely *= -1
   324  }
   325  
   326  // removePhiArg removes the ith arg from phi.
   327  // It must be called after calling b.removePred(i) to
   328  // adjust the corresponding phi value of the block:
   329  //
   330  // b.removePred(i)
   331  // for _, v := range b.Values {
   332  //     if v.Op != OpPhi {
   333  //         continue
   334  //     }
   335  //     b.removeArg(v, i)
   336  // }
   337  func (b *Block) removePhiArg(phi *Value, i int) {
   338  	n := len(b.Preds)
   339  	if numPhiArgs := len(phi.Args); numPhiArgs-1 != n {
   340  		b.Fatalf("inconsistent state, num predecessors: %d, num phi args: %d", n, numPhiArgs)
   341  	}
   342  	phi.Args[i].Uses--
   343  	phi.Args[i] = phi.Args[n]
   344  	phi.Args[n] = nil
   345  	phi.Args = phi.Args[:n]
   346  }
   347  
   348  // LackingPos indicates whether b is a block whose position should be inherited
   349  // from its successors.  This is true if all the values within it have unreliable positions
   350  // and if it is "plain", meaning that there is no control flow that is also very likely
   351  // to correspond to a well-understood source position.
   352  func (b *Block) LackingPos() bool {
   353  	// Non-plain predecessors are If or Defer, which both (1) have two successors,
   354  	// which might have different line numbers and (2) correspond to statements
   355  	// in the source code that have positions, so this case ought not occur anyway.
   356  	if b.Kind != BlockPlain {
   357  		return false
   358  	}
   359  	if b.Pos != src.NoXPos {
   360  		return false
   361  	}
   362  	for _, v := range b.Values {
   363  		if v.LackingPos() {
   364  			continue
   365  		}
   366  		return false
   367  	}
   368  	return true
   369  }
   370  
   371  func (b *Block) AuxIntString() string {
   372  	switch b.Kind.AuxIntType() {
   373  	case "int8":
   374  		return fmt.Sprintf("%v", int8(b.AuxInt))
   375  	case "uint8":
   376  		return fmt.Sprintf("%v", uint8(b.AuxInt))
   377  	default: // type specified but not implemented - print as int64
   378  		return fmt.Sprintf("%v", b.AuxInt)
   379  	case "": // no aux int type
   380  		return ""
   381  	}
   382  }
   383  
   384  // likelyBranch reports whether block b is the likely branch of all of its predecessors.
   385  func (b *Block) likelyBranch() bool {
   386  	if len(b.Preds) == 0 {
   387  		return false
   388  	}
   389  	for _, e := range b.Preds {
   390  		p := e.b
   391  		if len(p.Succs) == 1 || len(p.Succs) == 2 && (p.Likely == BranchLikely && p.Succs[0].b == b ||
   392  			p.Likely == BranchUnlikely && p.Succs[1].b == b) {
   393  			continue
   394  		}
   395  		return false
   396  	}
   397  	return true
   398  }
   399  
   400  func (b *Block) Logf(msg string, args ...interface{})   { b.Func.Logf(msg, args...) }
   401  func (b *Block) Log() bool                              { return b.Func.Log() }
   402  func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) }
   403  
   404  type BranchPrediction int8
   405  
   406  const (
   407  	BranchUnlikely = BranchPrediction(-1)
   408  	BranchUnknown  = BranchPrediction(0)
   409  	BranchLikely   = BranchPrediction(+1)
   410  )
   411
View as plain text