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  	// What cpu features (AVXnnn, SVEyyy) are implied to reach/execute this block?
    22  	CPUfeatures CPUfeatures
    23  
    24  	// The kind of block this is.
    25  	Kind BlockKind
    26  
    27  	// Likely direction for branches.
    28  	// If BranchLikely, Succs[0] is the most likely branch taken.
    29  	// If BranchUnlikely, Succs[1] is the most likely branch taken.
    30  	// Ignored if len(Succs) < 2.
    31  	// Fatal if not BranchUnknown and len(Succs) > 2.
    32  	Likely BranchPrediction
    33  
    34  	// After flagalloc, records whether flags are live at the end of the block.
    35  	FlagsLiveAtEnd bool
    36  
    37  	// A block that would be good to align (according to the optimizer's guesses)
    38  	Hotness Hotness
    39  
    40  	// Subsequent blocks, if any. The number and order depend on the block kind.
    41  	Succs []Edge
    42  
    43  	// Inverse of successors.
    44  	// The order is significant to Phi nodes in the block.
    45  	// TODO: predecessors is a pain to maintain. Can we somehow order phi
    46  	// arguments by block id and have this field computed explicitly when needed?
    47  	Preds []Edge
    48  
    49  	// A list of values that determine how the block is exited. The number
    50  	// and type of control values depends on the Kind of the block. For
    51  	// instance, a BlockIf has a single boolean control value and BlockExit
    52  	// has a single memory control value.
    53  	//
    54  	// The ControlValues() method may be used to get a slice with the non-nil
    55  	// control values that can be ranged over.
    56  	//
    57  	// Controls[1] must be nil if Controls[0] is nil.
    58  	Controls [2]*Value
    59  
    60  	// Auxiliary info for the block. Its value depends on the Kind.
    61  	Aux    Aux
    62  	AuxInt int64
    63  
    64  	// The unordered set of Values that define the operation of this block.
    65  	// After the scheduling pass, this list is ordered.
    66  	Values []*Value
    67  
    68  	// The containing function
    69  	Func *Func
    70  
    71  	// Storage for Succs, Preds and Values.
    72  	succstorage [2]Edge
    73  	predstorage [4]Edge
    74  	valstorage  [9]*Value
    75  }
    76  
    77  // Edge represents a CFG edge.
    78  // Example edges for b branching to either c or d.
    79  // (c and d have other predecessors.)
    80  //
    81  //	b.Succs = [{c,3}, {d,1}]
    82  //	c.Preds = [?, ?, ?, {b,0}]
    83  //	d.Preds = [?, {b,1}, ?]
    84  //
    85  // These indexes allow us to edit the CFG in constant time.
    86  // In addition, it informs phi ops in degenerate cases like:
    87  //
    88  //	b:
    89  //	   if k then c else c
    90  //	c:
    91  //	   v = Phi(x, y)
    92  //
    93  // Then the indexes tell you whether x is chosen from
    94  // the if or else branch from b.
    95  //
    96  //	b.Succs = [{c,0},{c,1}]
    97  //	c.Preds = [{b,0},{b,1}]
    98  //
    99  // means x is chosen if k is true.
   100  type Edge struct {
   101  	// block edge goes to (in a Succs list) or from (in a Preds list)
   102  	b *Block
   103  	// index of reverse edge.  Invariant:
   104  	//   e := x.Succs[idx]
   105  	//   e.b.Preds[e.i] = Edge{x,idx}
   106  	// and similarly for predecessors.
   107  	i int
   108  }
   109  
   110  func (e Edge) Block() *Block {
   111  	return e.b
   112  }
   113  func (e Edge) Index() int {
   114  	return e.i
   115  }
   116  func (e Edge) String() string {
   117  	return fmt.Sprintf("{%v,%d}", e.b, e.i)
   118  }
   119  
   120  // BlockKind is the kind of SSA block.
   121  type BlockKind uint8
   122  
   123  // short form print
   124  func (b *Block) String() string {
   125  	return fmt.Sprintf("b%d", b.ID)
   126  }
   127  
   128  // long form print
   129  func (b *Block) LongString() string {
   130  	s := b.Kind.String()
   131  	if b.Aux != nil {
   132  		s += fmt.Sprintf(" {%s}", b.Aux)
   133  	}
   134  	if t := b.AuxIntString(); t != "" {
   135  		s += fmt.Sprintf(" [%s]", t)
   136  	}
   137  	for _, c := range b.ControlValues() {
   138  		s += fmt.Sprintf(" %s", c)
   139  	}
   140  	if len(b.Succs) > 0 {
   141  		s += " ->"
   142  		for _, c := range b.Succs {
   143  			s += " " + c.b.String()
   144  		}
   145  	}
   146  	switch b.Likely {
   147  	case BranchUnlikely:
   148  		s += " (unlikely)"
   149  	case BranchLikely:
   150  		s += " (likely)"
   151  	}
   152  	return s
   153  }
   154  
   155  // NumControls returns the number of non-nil control values the
   156  // block has.
   157  func (b *Block) NumControls() int {
   158  	if b.Controls[0] == nil {
   159  		return 0
   160  	}
   161  	if b.Controls[1] == nil {
   162  		return 1
   163  	}
   164  	return 2
   165  }
   166  
   167  // ControlValues returns a slice containing the non-nil control
   168  // values of the block. The index of each control value will be
   169  // the same as it is in the Controls property and can be used
   170  // in ReplaceControl calls.
   171  func (b *Block) ControlValues() []*Value {
   172  	if b.Controls[0] == nil {
   173  		return b.Controls[:0]
   174  	}
   175  	if b.Controls[1] == nil {
   176  		return b.Controls[:1]
   177  	}
   178  	return b.Controls[:2]
   179  }
   180  
   181  // SetControl removes all existing control values and then adds
   182  // the control value provided. The number of control values after
   183  // a call to SetControl will always be 1.
   184  func (b *Block) SetControl(v *Value) {
   185  	b.ResetControls()
   186  	b.Controls[0] = v
   187  	v.Uses++
   188  }
   189  
   190  // ResetControls sets the number of controls for the block to 0.
   191  func (b *Block) ResetControls() {
   192  	if b.Controls[0] != nil {
   193  		b.Controls[0].Uses--
   194  	}
   195  	if b.Controls[1] != nil {
   196  		b.Controls[1].Uses--
   197  	}
   198  	b.Controls = [2]*Value{} // reset both controls to nil
   199  }
   200  
   201  // AddControl appends a control value to the existing list of control values.
   202  func (b *Block) AddControl(v *Value) {
   203  	i := b.NumControls()
   204  	b.Controls[i] = v // panics if array is full
   205  	v.Uses++
   206  }
   207  
   208  // ReplaceControl exchanges the existing control value at the index provided
   209  // for the new value. The index must refer to a valid control value.
   210  func (b *Block) ReplaceControl(i int, v *Value) {
   211  	b.Controls[i].Uses--
   212  	b.Controls[i] = v
   213  	v.Uses++
   214  }
   215  
   216  // CopyControls replaces the controls for this block with those from the
   217  // provided block. The provided block is not modified.
   218  func (b *Block) CopyControls(from *Block) {
   219  	if b == from {
   220  		return
   221  	}
   222  	b.ResetControls()
   223  	for _, c := range from.ControlValues() {
   224  		b.AddControl(c)
   225  	}
   226  }
   227  
   228  // Reset sets the block to the provided kind and clears all the blocks control
   229  // and auxiliary values. Other properties of the block, such as its successors,
   230  // predecessors and values are left unmodified.
   231  func (b *Block) Reset(kind BlockKind) {
   232  	b.Kind = kind
   233  	b.ResetControls()
   234  	b.Aux = nil
   235  	b.AuxInt = 0
   236  }
   237  
   238  // resetWithControl resets b and adds control v.
   239  // It is equivalent to b.Reset(kind); b.AddControl(v),
   240  // except that it is one call instead of two and avoids a bounds check.
   241  // It is intended for use by rewrite rules, where this matters.
   242  func (b *Block) resetWithControl(kind BlockKind, v *Value) {
   243  	b.Kind = kind
   244  	b.ResetControls()
   245  	b.Aux = nil
   246  	b.AuxInt = 0
   247  	b.Controls[0] = v
   248  	v.Uses++
   249  }
   250  
   251  // resetWithControl2 resets b and adds controls v and w.
   252  // It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w),
   253  // except that it is one call instead of three and avoids two bounds checks.
   254  // It is intended for use by rewrite rules, where this matters.
   255  func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) {
   256  	b.Kind = kind
   257  	b.ResetControls()
   258  	b.Aux = nil
   259  	b.AuxInt = 0
   260  	b.Controls[0] = v
   261  	b.Controls[1] = w
   262  	v.Uses++
   263  	w.Uses++
   264  }
   265  
   266  // truncateValues truncates b.Values at the ith element, zeroing subsequent elements.
   267  // The values in b.Values after i must already have had their args reset,
   268  // to maintain correct value uses counts.
   269  func (b *Block) truncateValues(i int) {
   270  	clear(b.Values[i:])
   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  // uniquePred returns the predecessor of b, if there is exactly one.
   370  // Returns nil otherwise.
   371  func (b *Block) uniquePred() *Block {
   372  	if len(b.Preds) != 1 {
   373  		return nil
   374  	}
   375  	return b.Preds[0].b
   376  }
   377  
   378  // LackingPos indicates whether b is a block whose position should be inherited
   379  // from its successors.  This is true if all the values within it have unreliable positions
   380  // and if it is "plain", meaning that there is no control flow that is also very likely
   381  // to correspond to a well-understood source position.
   382  func (b *Block) LackingPos() bool {
   383  	// Non-plain predecessors are If or Defer, which both (1) have two successors,
   384  	// which might have different line numbers and (2) correspond to statements
   385  	// in the source code that have positions, so this case ought not occur anyway.
   386  	if b.Kind != BlockPlain {
   387  		return false
   388  	}
   389  	if b.Pos != src.NoXPos {
   390  		return false
   391  	}
   392  	for _, v := range b.Values {
   393  		if v.LackingPos() {
   394  			continue
   395  		}
   396  		return false
   397  	}
   398  	return true
   399  }
   400  
   401  func (b *Block) AuxIntString() string {
   402  	switch b.Kind.AuxIntType() {
   403  	case "int8":
   404  		return fmt.Sprintf("%v", int8(b.AuxInt))
   405  	case "uint8":
   406  		return fmt.Sprintf("%v", uint8(b.AuxInt))
   407  	case "": // no aux int type
   408  		return ""
   409  	default: // type specified but not implemented - print as int64
   410  		return fmt.Sprintf("%v", b.AuxInt)
   411  	}
   412  }
   413  
   414  // likelyBranch reports whether block b is the likely branch of all of its predecessors.
   415  func (b *Block) likelyBranch() bool {
   416  	if len(b.Preds) == 0 {
   417  		return false
   418  	}
   419  	for _, e := range b.Preds {
   420  		p := e.b
   421  		if len(p.Succs) == 1 || len(p.Succs) == 2 && (p.Likely == BranchLikely && p.Succs[0].b == b ||
   422  			p.Likely == BranchUnlikely && p.Succs[1].b == b) {
   423  			continue
   424  		}
   425  		return false
   426  	}
   427  	return true
   428  }
   429  
   430  func (b *Block) Logf(msg string, args ...any)   { b.Func.Logf(msg, args...) }
   431  func (b *Block) Log() bool                      { return b.Func.Log() }
   432  func (b *Block) Fatalf(msg string, args ...any) { b.Func.Fatalf(msg, args...) }
   433  
   434  type BranchPrediction int8
   435  
   436  const (
   437  	BranchUnlikely = BranchPrediction(-1)
   438  	BranchUnknown  = BranchPrediction(0)
   439  	BranchLikely   = BranchPrediction(+1)
   440  )
   441  
   442  type Hotness int8 // Could use negative numbers for specifically non-hot blocks, but don't, yet.
   443  const (
   444  	// These values are arranged in what seems to be order of increasing alignment importance.
   445  	// Currently only a few are relevant.  Implicitly, they are all in a loop.
   446  	HotNotFlowIn Hotness = 1 << iota // This block is only reached by branches
   447  	HotInitial                       // In the block order, the first one for a given loop.  Not necessarily topological header.
   448  	HotPgo                           // By PGO-based heuristics, this block occurs in a hot loop
   449  
   450  	HotNot                 = 0
   451  	HotInitialNotFlowIn    = HotInitial | HotNotFlowIn          // typically first block of a rotated loop, loop is entered with a branch (not to this block).  No PGO
   452  	HotPgoInitial          = HotPgo | HotInitial                // special case; single block loop, initial block is header block has a flow-in entry, but PGO says it is hot
   453  	HotPgoInitialNotFLowIn = HotPgo | HotInitial | HotNotFlowIn // PGO says it is hot, and the loop is rotated so flow enters loop with a branch
   454  )
   455  
   456  type CPUfeatures uint32
   457  
   458  const (
   459  	CPUNone CPUfeatures = 0
   460  	CPUAll  CPUfeatures = ^CPUfeatures(0)
   461  	CPUavx  CPUfeatures = 1 << iota
   462  	CPUavx2
   463  	CPUavxvnni
   464  	CPUavx512
   465  	CPUbitalg
   466  	CPUgfni
   467  	CPUvbmi
   468  	CPUvbmi2
   469  	CPUvpopcntdq
   470  	CPUavx512vnni
   471  
   472  	CPUneon
   473  	CPUsve2
   474  )
   475  
   476  func (f CPUfeatures) hasFeature(x CPUfeatures) bool {
   477  	return f&x == x
   478  }
   479  
   480  func (f CPUfeatures) String() string {
   481  	if f == CPUNone {
   482  		return "none"
   483  	}
   484  	if f == CPUAll {
   485  		return "all"
   486  	}
   487  	s := ""
   488  	foo := func(what string, feat CPUfeatures) {
   489  		if feat&f != 0 {
   490  			if s != "" {
   491  				s += "+"
   492  			}
   493  			s += what
   494  		}
   495  	}
   496  	foo("avx", CPUavx)
   497  	foo("avx2", CPUavx2)
   498  	foo("avx512", CPUavx512)
   499  	foo("avxvnni", CPUavxvnni)
   500  	foo("bitalg", CPUbitalg)
   501  	foo("gfni", CPUgfni)
   502  	foo("vbmi", CPUvbmi)
   503  	foo("vbmi2", CPUvbmi2)
   504  	foo("popcntdq", CPUvpopcntdq)
   505  	foo("avx512vnni", CPUavx512vnni)
   506  
   507  	return s
   508  }
   509
View as plain text