[gostls13.git] / 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.removePhiArg(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]
        phielimValue(phi)
}

// 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)
)