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