File Manager

X7ROOT File Manager

Current Path: /opt/golang/1.19.4/src/cmd/compile/internal/ssa

opt / golang / 1.19.4 / src / cmd / compile / internal / ssa /

📁 ..
📄 README.md(8.14 KB)
📄 TODO(950 B)
📄 addressingmodes.go(23.64 KB)
📄 bench_test.go(531 B)
📄 biasedsparsemap.go(2.71 KB)
📄 block.go(11.1 KB)
📄 branchelim.go(11.98 KB)
📄 branchelim_test.go(5.21 KB)
📄 cache.go(2.46 KB)
📄 check.go(16.59 KB)
📄 checkbce.go(956 B)
📄 compile.go(18.19 KB)
📄 config.go(11.7 KB)
📄 copyelim.go(1.83 KB)
📄 copyelim_test.go(1.29 KB)
📄 critical.go(3.19 KB)
📄 cse.go(9.43 KB)
📄 cse_test.go(4.25 KB)
📄 deadcode.go(9.61 KB)
📄 deadcode_test.go(3.49 KB)
📄 deadstore.go(9.08 KB)
📄 deadstore_test.go(4.09 KB)
📄 debug.go(56.34 KB)
📄 debug_lines_test.go(8.29 KB)
📄 debug_test.go(28.75 KB)
📄 decompose.go(13.41 KB)
📄 dom.go(7.98 KB)
📄 dom_test.go(13.34 KB)
📄 expand_calls.go(63.5 KB)
📄 export_test.go(3.23 KB)
📄 flagalloc.go(6.68 KB)
📄 flags_amd64_test.s(533 B)
📄 flags_arm64_test.s(699 B)
📄 flags_test.go(2.49 KB)
📄 func.go(27.08 KB)
📄 func_test.go(13.07 KB)
📄 fuse.go(6.5 KB)
📄 fuse_branchredirect.go(3.24 KB)
📄 fuse_comparisons.go(4.04 KB)
📄 fuse_test.go(7.21 KB)
📁 gen
📄 html.go(34.72 KB)
📄 id.go(576 B)
📄 layout.go(4.82 KB)
📄 lca.go(3.77 KB)
📄 lca_test.go(1.65 KB)
📄 likelyadjust.go(15.24 KB)
📄 location.go(3.06 KB)
📄 loopbce.go(10.54 KB)
📄 loopreschedchecks.go(15.86 KB)
📄 looprotate.go(2.61 KB)
📄 lower.go(1.36 KB)
📄 magic.go(15.77 KB)
📄 magic_test.go(9.1 KB)
📄 nilcheck.go(11.06 KB)
📄 nilcheck_test.go(12.17 KB)
📄 numberlines.go(7.83 KB)
📄 op.go(18.65 KB)
📄 opGen.go(1.01 MB)
📄 opt.go(308 B)
📄 passbm_test.go(3.14 KB)
📄 phielim.go(1.48 KB)
📄 phiopt.go(8.08 KB)
📄 poset.go(37.2 KB)
📄 poset_test.go(18.14 KB)
📄 print.go(3.85 KB)
📄 prove.go(41.82 KB)
📄 regalloc.go(83.69 KB)
📄 regalloc_test.go(6.49 KB)
📄 rewrite.go(53.49 KB)
📄 rewrite386.go(289.01 KB)
📄 rewrite386splitload.go(4.05 KB)
📄 rewriteAMD64.go(888.95 KB)
📄 rewriteAMD64splitload.go(21.41 KB)
📄 rewriteARM.go(487.7 KB)
📄 rewriteARM64.go(751.84 KB)
📄 rewriteCond_test.go(10.62 KB)
📄 rewriteLOONG64.go(193.44 KB)
📄 rewriteMIPS.go(174.44 KB)
📄 rewriteMIPS64.go(195.55 KB)
📄 rewritePPC64.go(431.6 KB)
📄 rewriteRISCV64.go(159.66 KB)
📄 rewriteS390X.go(433.4 KB)
📄 rewriteWasm.go(109.86 KB)
📄 rewrite_test.go(6.91 KB)
📄 rewritedec.go(10.16 KB)
📄 rewritedec64.go(63.77 KB)
📄 rewritegeneric.go(617.96 KB)
📄 schedule.go(18.23 KB)
📄 schedule_test.go(2.91 KB)
📄 shift_test.go(4.05 KB)
📄 shortcircuit.go(12.63 KB)
📄 shortcircuit_test.go(1.31 KB)
📄 sizeof_test.go(855 B)
📄 softfloat.go(1.99 KB)
📄 sparsemap.go(1.98 KB)
📄 sparseset.go(1.54 KB)
📄 sparsetree.go(8.05 KB)
📄 stackalloc.go(12.79 KB)
📄 stackframe.go(290 B)
📄 stmtlines_test.go(2.96 KB)
📁 testdata
📄 tighten.go(4.3 KB)
📄 trim.go(4.24 KB)
📄 tuple.go(1.97 KB)
📄 value.go(15.21 KB)
📄 writebarrier.go(19.29 KB)
📄 writebarrier_test.go(1.75 KB)
📄 xposmap.go(3.29 KB)
📄 zcse.go(2.07 KB)
📄 zeroextension_test.go(1.66 KB)

Editing: sparsetree.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 (
	"fmt"
	"strings"
)

type SparseTreeNode struct {
	child   *Block
	sibling *Block
	parent  *Block

// Every block has 6 numbers associated with it:
	// entry-1, entry, entry+1, exit-1, and exit, exit+1.
	// entry and exit are conceptually the top of the block (phi functions)
	// entry+1 and exit-1 are conceptually the bottom of the block (ordinary defs)
	// entry-1 and exit+1 are conceptually "just before" the block (conditions flowing in)
	//
	// This simplifies life if we wish to query information about x
	// when x is both an input to and output of a block.
	entry, exit int32
}

func (s *SparseTreeNode) String() string {
	return fmt.Sprintf("[%d,%d]", s.entry, s.exit)
}

func (s *SparseTreeNode) Entry() int32 {
	return s.entry
}

func (s *SparseTreeNode) Exit() int32 {
	return s.exit
}

const (
	// When used to lookup up definitions in a sparse tree,
	// these adjustments to a block's entry (+adjust) and
	// exit (-adjust) numbers allow a distinction to be made
	// between assignments (typically branch-dependent
	// conditionals) occurring "before" the block (e.g., as inputs
	// to the block and its phi functions), "within" the block,
	// and "after" the block.
	AdjustBefore = -1 // defined before phi
	AdjustWithin = 0  // defined by phi
	AdjustAfter  = 1  // defined within block
)

// A SparseTree is a tree of Blocks.
// It allows rapid ancestor queries,
// such as whether one block dominates another.
type SparseTree []SparseTreeNode

// newSparseTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID)
func newSparseTree(f *Func, parentOf []*Block) SparseTree {
	t := make(SparseTree, f.NumBlocks())
	for _, b := range f.Blocks {
		n := &t[b.ID]
		if p := parentOf[b.ID]; p != nil {
			n.parent = p
			n.sibling = t[p.ID].child
			t[p.ID].child = b
		}
	}
	t.numberBlock(f.Entry, 1)
	return t
}

// newSparseOrderedTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID)
// children will appear in the reverse of their order in reverseOrder
// in particular, if reverseOrder is a dfs-reversePostOrder, then the root-to-children
// walk of the tree will yield a pre-order.
func newSparseOrderedTree(f *Func, parentOf, reverseOrder []*Block) SparseTree {
	t := make(SparseTree, f.NumBlocks())
	for _, b := range reverseOrder {
		n := &t[b.ID]
		if p := parentOf[b.ID]; p != nil {
			n.parent = p
			n.sibling = t[p.ID].child
			t[p.ID].child = b
		}
	}
	t.numberBlock(f.Entry, 1)
	return t
}

// treestructure provides a string description of the dominator
// tree and flow structure of block b and all blocks that it
// dominates.
func (t SparseTree) treestructure(b *Block) string {
	return t.treestructure1(b, 0)
}
func (t SparseTree) treestructure1(b *Block, i int) string {
	s := "\n" + strings.Repeat("\t", i) + b.String() + "->["
	for i, e := range b.Succs {
		if i > 0 {
			s += ","
		}
		s += e.b.String()
	}
	s += "]"
	if c0 := t[b.ID].child; c0 != nil {
		s += "("
		for c := c0; c != nil; c = t[c.ID].sibling {
			if c != c0 {
				s += " "
			}
			s += t.treestructure1(c, i+1)
		}
		s += ")"
	}
	return s
}

// numberBlock assigns entry and exit numbers for b and b's
// children in an in-order walk from a gappy sequence, where n
// is the first number not yet assigned or reserved. N should
// be larger than zero. For each entry and exit number, the
// values one larger and smaller are reserved to indicate
// "strictly above" and "strictly below". numberBlock returns
// the smallest number not yet assigned or reserved (i.e., the
// exit number of the last block visited, plus two, because
// last.exit+1 is a reserved value.)
//
// examples:
//
// single node tree Root, call with n=1
//         entry=2 Root exit=5; returns 7
//
// two node tree, Root->Child, call with n=1
//         entry=2 Root exit=11; returns 13
//         entry=5 Child exit=8
//
// three node tree, Root->(Left, Right), call with n=1
//         entry=2 Root exit=17; returns 19
// entry=5 Left exit=8;  entry=11 Right exit=14
//
// This is the in-order sequence of assigned and reserved numbers
// for the last example:
//   root     left     left      right       right       root
//  1 2e 3 | 4 5e 6 | 7 8x 9 | 10 11e 12 | 13 14x 15 | 16 17x 18

func (t SparseTree) numberBlock(b *Block, n int32) int32 {
	// reserve n for entry-1, assign n+1 to entry
	n++
	t[b.ID].entry = n
	// reserve n+1 for entry+1, n+2 is next free number
	n += 2
	for c := t[b.ID].child; c != nil; c = t[c.ID].sibling {
		n = t.numberBlock(c, n) // preserves n = next free number
	}
	// reserve n for exit-1, assign n+1 to exit
	n++
	t[b.ID].exit = n
	// reserve n+1 for exit+1, n+2 is next free number, returned.
	return n + 2
}

// Sibling returns a sibling of x in the dominator tree (i.e.,
// a node with the same immediate dominator) or nil if there
// are no remaining siblings in the arbitrary but repeatable
// order chosen. Because the Child-Sibling order is used
// to assign entry and exit numbers in the treewalk, those
// numbers are also consistent with this order (i.e.,
// Sibling(x) has entry number larger than x's exit number).
func (t SparseTree) Sibling(x *Block) *Block {
	return t[x.ID].sibling
}

// Child returns a child of x in the dominator tree, or
// nil if there are none. The choice of first child is
// arbitrary but repeatable.
func (t SparseTree) Child(x *Block) *Block {
	return t[x.ID].child
}

// Parent returns the parent of x in the dominator tree, or
// nil if x is the function's entry.
func (t SparseTree) Parent(x *Block) *Block {
	return t[x.ID].parent
}

// isAncestorEq reports whether x is an ancestor of or equal to y.
func (t SparseTree) IsAncestorEq(x, y *Block) bool {
	if x == y {
		return true
	}
	xx := &t[x.ID]
	yy := &t[y.ID]
	return xx.entry <= yy.entry && yy.exit <= xx.exit
}

// isAncestor reports whether x is a strict ancestor of y.
func (t SparseTree) isAncestor(x, y *Block) bool {
	if x == y {
		return false
	}
	xx := &t[x.ID]
	yy := &t[y.ID]
	return xx.entry < yy.entry && yy.exit < xx.exit
}

// domorder returns a value for dominator-oriented sorting.
// Block domination does not provide a total ordering,
// but domorder two has useful properties.
//  1. If domorder(x) > domorder(y) then x does not dominate y.
//  2. If domorder(x) < domorder(y) and domorder(y) < domorder(z) and x does not dominate y,
//     then x does not dominate z.
//
// Property (1) means that blocks sorted by domorder always have a maximal dominant block first.
// Property (2) allows searches for dominated blocks to exit early.
func (t SparseTree) domorder(x *Block) int32 {
	// Here is an argument that entry(x) provides the properties documented above.
	//
	// Entry and exit values are assigned in a depth-first dominator tree walk.
	// For all blocks x and y, one of the following holds:
	//
	// (x-dom-y) x dominates y => entry(x) < entry(y) < exit(y) < exit(x)
	// (y-dom-x) y dominates x => entry(y) < entry(x) < exit(x) < exit(y)
	// (x-then-y) neither x nor y dominates the other and x walked before y => entry(x) < exit(x) < entry(y) < exit(y)
	// (y-then-x) neither x nor y dominates the other and y walked before y => entry(y) < exit(y) < entry(x) < exit(x)
	//
	// entry(x) > entry(y) eliminates case x-dom-y. This provides property (1) above.
	//
	// For property (2), assume entry(x) < entry(y) and entry(y) < entry(z) and x does not dominate y.
	// entry(x) < entry(y) allows cases x-dom-y and x-then-y.
	// But by supposition, x does not dominate y. So we have x-then-y.
	//
	// For contradiction, assume x dominates z.
	// Then entry(x) < entry(z) < exit(z) < exit(x).
	// But we know x-then-y, so entry(x) < exit(x) < entry(y) < exit(y).
	// Combining those, entry(x) < entry(z) < exit(z) < exit(x) < entry(y) < exit(y).
	// By supposition, entry(y) < entry(z), which allows cases y-dom-z and y-then-z.
	// y-dom-z requires entry(y) < entry(z), but we have entry(z) < entry(y).
	// y-then-z requires exit(y) < entry(z), but we have entry(z) < exit(y).
	// We have a contradiction, so x does not dominate z, as required.
	return t[x.ID].entry
}

X7ROOT File Manager

Editing: sparsetree.go

Upload File

Create Folder