golang block 代码
文件路径：/src/cmd/compile/internal/ssa/block.go
/ Copyright 2015 The Go Authors. All rights reserved.
/ Use of this source code is governed by a BSD-style
/ license that can be found in the LICENSE file.
package ssa
import (
"cmd/internal/src"
"fmt"
)
/ Block represents a basic block in the control flow graph of a function.
type Block struct {
/ A unique identifier for the block. The system will attempt to allocate
/ these IDs densely, but no guarantees.
ID ID
/ Source position for block's control operation
Pos src.XPos
/ The kind of block this is.
Kind BlockKind
/ Likely direction for branches.
/ If BranchLikely, Succs[0] is the most likely branch taken.
/ If BranchUnlikely, Succs[1] is the most likely branch taken.
/ Ignored if len(Succs) < 2.
/ Fatal if not BranchUnknown and len(Succs) > 2.
Likely BranchPrediction
/ After flagalloc, records whether flags are live at the end of the block.
FlagsLiveAtEnd bool
/ Subsequent blocks, if any. The number and order depend on the block kind.
Succs []Edge
/ Inverse of successors.
/ The order is significant to Phi nodes in the block.
/ TODO: predecessors is a pain to maintain. Can we somehow order phi
/ arguments by block id and have this field computed explicitly when needed?
Preds []Edge
/ A list of values that determine how the block is exited. The number
/ and type of control values depends on the Kind of the block. For
/ instance, a BlockIf has a single boolean control value and BlockExit
/ has a single memory control value.
/
/ The ControlValues() method may be used to get a slice with the non-nil
/ control values that can be ranged over.
/
/ Controls[1] must be nil if Controls[0] is nil.
Controls [2]*Value
/ Auxiliary info for the block. Its value depends on the Kind.
Aux Aux
AuxInt int64
/ The unordered set of Values that define the operation of this block.
/ After the scheduling pass, this list is ordered.
Values []*Value
/ The containing function
Func *Func
/ Storage for Succs, Preds and Values.
succstorage [2]Edge
predstorage [4]Edge
valstorage [9]*Value
}
/ Edge represents a CFG edge.
/ Example edges for b branching to either c or d.
/ (c and d have other predecessors.)
/
/ b.Succs = [{c,3}, {d,1}]
/ c.Preds = [?, ?, ?, {b,0}]
/ d.Preds = [?, {b,1}, ?]
/
/ These indexes allow us to edit the CFG in constant time.
/ In addition, it informs phi ops in degenerate cases like:
/
/ b:
/ if k then c else c
/ c:
/ v = Phi(x, y)
/
/ Then the indexes tell you whether x is chosen from
/ the if or else branch from b.
/
/ b.Succs = [{c,0},{c,1}]
/ c.Preds = [{b,0},{b,1}]
/
/ means x is chosen if k is true.
type Edge struct {
/ block edge goes to (in a Succs list) or from (in a Preds list)
b *Block
/ index of reverse edge. Invariant:
/ e := x.Succs[idx]
/ e.b.Preds[e.i] = Edge{x,idx}
/ and similarly for predecessors.
i int
}
func (e Edge) Block() *Block {
return e.b
}
func (e Edge) Index() int {
return e.i
}
func (e Edge) String() string {
return fmt.Sprintf("{%v,%d}", e.b, e.i)
}
/ BlockKind is the kind of SSA block.
/
/ kind controls successors
/ ------------------------------------------
/ Exit [return mem] []
/ Plain [] [next]
/ If [boolean Value] [then, else]
/ Defer [mem] [nopanic, panic] (control opcode should be OpStaticCall to runtime.deferproc)
type BlockKind int16
/ short form print
func (b *Block) String() string {
return fmt.Sprintf("b%d", b.ID)
}
/ long form print
func (b *Block) LongString() string {
s := b.Kind.String()
if b.Aux != nil {
s += fmt.Sprintf(" {%s}", b.Aux)
}
if t := b.AuxIntString(); t != "" {
s += fmt.Sprintf(" [%s]", t)
}
for _, c := range b.ControlValues() {
s += fmt.Sprintf(" %s", c)
}
if len(b.Succs) > 0 {
s += " ->"
for _, c := range b.Succs {
s += " " + c.b.String()
}
}
switch b.Likely {
case BranchUnlikely:
s += " (unlikely)"
case BranchLikely:
s += " (likely)"
}
return s
}
/ NumControls returns the number of non-nil control values the
/ block has.
func (b *Block) NumControls() int {
if b.Controls[0] == nil {
return 0
}
if b.Controls[1] == nil {
return 1
}
return 2
}
/ ControlValues returns a slice containing the non-nil control
/ values of the block. The index of each control value will be
/ the same as it is in the Controls property and can be used
/ in ReplaceControl calls.
func (b *Block) ControlValues() []*Value {
if b.Controls[0] == nil {
return b.Controls[:0]
}
if b.Controls[1] == nil {
return b.Controls[:1]
}
return b.Controls[:2]
}
/ SetControl removes all existing control values and then adds
/ the control value provided. The number of control values after
/ a call to SetControl will always be 1.
func (b *Block) SetControl(v *Value) {
b.ResetControls()
b.Controls[0] = v
v.Uses++
}
/ ResetControls sets the number of controls for the block to 0.
func (b *Block) ResetControls() {
if b.Controls[0] != nil {
b.Controls[0].Uses--
}
if b.Controls[1] != nil {
b.Controls[1].Uses--
}
b.Controls = [2]*Value{} / reset both controls to nil
}
/ AddControl appends a control value to the existing list of control values.
func (b *Block) AddControl(v *Value) {
i := b.NumControls()
b.Controls[i] = v / panics if array is full
v.Uses++
}
/ ReplaceControl exchanges the existing control value at the index provided
/ for the new value. The index must refer to a valid control value.
func (b *Block) ReplaceControl(i int, v *Value) {
b.Controls[i].Uses--
b.Controls[i] = v
v.Uses++
}
/ CopyControls replaces the controls for this block with those from the
/ provided block. The provided block is not modified.
func (b *Block) CopyControls(from *Block) {
if b == from {
return
}
b.ResetControls()
for _, c := range from.ControlValues() {
b.AddControl(c)
}
}
/ Reset sets the block to the provided kind and clears all the blocks control
/ and auxiliary values. Other properties of the block, such as its successors,
/ predecessors and values are left unmodified.
func (b *Block) Reset(kind BlockKind) {
b.Kind = kind
b.ResetControls()
b.Aux = nil
b.AuxInt = 0
}
/ resetWithControl resets b and adds control v.
/ It is equivalent to b.Reset(kind); b.AddControl(v),
/ except that it is one call instead of two and avoids a bounds check.
/ It is intended for use by rewrite rules, where this matters.
func (b *Block) resetWithControl(kind BlockKind, v *Value) {
b.Kind = kind
b.ResetControls()
b.Aux = nil
b.AuxInt = 0
b.Controls[0] = v
v.Uses++
}
/ resetWithControl2 resets b and adds controls v and w.
/ It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w),
/ except that it is one call instead of three and avoids two bounds checks.
/ It is intended for use by rewrite rules, where this matters.
func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) {
b.Kind = kind
b.ResetControls()
b.Aux = nil
b.AuxInt = 0
b.Controls[0] = v
b.Controls[1] = w
v.Uses++
w.Uses++
}
/ truncateValues truncates b.Values at the ith element, zeroing subsequent elements.
/ The values in b.Values after i must already have had their args reset,
/ to maintain correct value uses counts.
func (b *Block) truncateValues(i int) {
tail := b.Values[i:]
for j := range tail {
tail[j] = nil
}
b.Values = b.Values[:i]
}
/ AddEdgeTo adds an edge from block b to block c. Used during building of the
/ SSA graph; do not use on an already-completed SSA graph.
func (b *Block) AddEdgeTo(c *Block) {
i := len(b.Succs)
j := len(c.Preds)
b.Succs = append(b.Succs, Edge{c, j})
c.Preds = append(c.Preds, Edge{b, i})
b.Func.invalidateCFG()
}
/ removePred removes the ith input edge from b.
/ It is the responsibility of the caller to remove
/ the corresponding successor edge, and adjust any
/ phi values by calling b.removePhiArg(v, i).
func (b *Block) removePred(i int) {
n := len(b.Preds) - 1
if i != n {
e := b.Preds[n]
b.Preds[i] = e
/ Update the other end of the edge we moved.
e.b.Succs[e.i].i = i
}
b.Preds[n] = Edge{}
b.Preds = b.Preds[:n]
b.Func.invalidateCFG()
}
/ removeSucc removes the ith output edge from b.
/ It is the responsibility of the caller to remove
/ the corresponding predecessor edge.
func (b *Block) removeSucc(i int) {
n := len(b.Succs) - 1
if i != n {
e := b.Succs[n]
b.Succs[i] = e
/ Update the other end of the edge we moved.
e.b.Preds[e.i].i = i
}
b.Succs[n] = Edge{}
b.Succs = b.Succs[:n]
b.Func.invalidateCFG()
}
func (b *Block) swapSuccessors() {
if len(b.Succs) != 2 {
b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs))
}
e0 := b.Succs[0]
e1 := b.Succs[1]
b.Succs[0] = e1
b.Succs[1] = e0
e0.b.Preds[e0.i].i = 1
e1.b.Preds[e1.i].i = 0
b.Likely *= -1
}
/ removePhiArg removes the ith arg from phi.
/ It must be called after calling b.removePred(i) to
/ adjust the corresponding phi value of the block:
/
/ b.removePred(i)
/ for _, v := range b.Values {
/
/ if v.Op != OpPhi {
/ continue
/ }
/ b.removeArg(v, i)
/
/ }
func (b *Block) removePhiArg(phi *Value, i int) {
n := len(b.Preds)
if numPhiArgs := len(phi.Args); numPhiArgs-1 != n {
b.Fatalf("inconsistent state, num predecessors: %d, num phi args: %d", n, numPhiArgs)
}
phi.Args[i].Uses--
phi.Args[i] = phi.Args[n]
phi.Args[n] = nil
phi.Args = phi.Args[:n]
}
/ LackingPos indicates whether b is a block whose position should be inherited
/ from its successors. This is true if all the values within it have unreliable positions
/ and if it is "plain", meaning that there is no control flow that is also very likely
/ to correspond to a well-understood source position.
func (b *Block) LackingPos() bool {
/ Non-plain predecessors are If or Defer, which both (1) have two successors,
/ which might have different line numbers and (2) correspond to statements
/ in the source code that have positions, so this case ought not occur anyway.
if b.Kind != BlockPlain {
return false
}
if b.Pos != src.NoXPos {
return false
}
for _, v := range b.Values {
if v.LackingPos() {
continue
}
return false
}
return true
}
func (b *Block) AuxIntString() string {
switch b.Kind.AuxIntType() {
case "int8":
return fmt.Sprintf("%v", int8(b.AuxInt))
case "uint8":
return fmt.Sprintf("%v", uint8(b.AuxInt))
default: / type specified but not implemented - print as int64
return fmt.Sprintf("%v", b.AuxInt)
case "": / no aux int type
return ""
}
}
/ likelyBranch reports whether block b is the likely branch of all of its predecessors.
func (b *Block) likelyBranch() bool {
if len(b.Preds) == 0 {
return false
}
for _, e := range b.Preds {
p := e.b
if len(p.Succs) == 1 || len(p.Succs) == 2 && (p.Likely == BranchLikely && p.Succs[0].b == b ||
p.Likely == BranchUnlikely && p.Succs[1].b == b) {
continue
}
return false
}
return true
}
func (b *Block) Logf(msg string, args ...interface{}) { b.Func.Logf(msg, args...) }
func (b *Block) Log() bool { return b.Func.Log() }
func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) }
type BranchPrediction int8
const (
BranchUnlikely = BranchPrediction(-1)
BranchUnknown = BranchPrediction(0)
BranchLikely = BranchPrediction(+1)
)