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