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