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: shortcircuit.go

// Copyright 2016 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

// Shortcircuit finds situations where branch directions
// are always correlated and rewrites the CFG to take
// advantage of that fact.
// This optimization is useful for compiling && and || expressions.
func shortcircuit(f *Func) {
	// Step 1: Replace a phi arg with a constant if that arg
	// is the control value of a preceding If block.
	// b1:
	//    If a goto b2 else b3
	// b2: <- b1 ...
	//    x = phi(a, ...)
	//
	// We can replace the "a" in the phi with the constant true.
	var ct, cf *Value
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if v.Op != OpPhi {
				continue
			}
			if !v.Type.IsBoolean() {
				continue
			}
			for i, a := range v.Args {
				e := b.Preds[i]
				p := e.b
				if p.Kind != BlockIf {
					continue
				}
				if p.Controls[0] != a {
					continue
				}
				if e.i == 0 {
					if ct == nil {
						ct = f.ConstBool(f.Config.Types.Bool, true)
					}
					v.SetArg(i, ct)
				} else {
					if cf == nil {
						cf = f.ConstBool(f.Config.Types.Bool, false)
					}
					v.SetArg(i, cf)
				}
			}
		}
	}

// Step 2: Redirect control flow around known branches.
	// p:
	//   ... goto b ...
	// b: <- p ...
	//   v = phi(true, ...)
	//   if v goto t else u
	// We can redirect p to go directly to t instead of b.
	// (If v is not live after b).
	fuse(f, fuseTypePlain|fuseTypeShortCircuit)
}

// shortcircuitBlock checks for a CFG in which an If block
// has as its control value a Phi that has a ConstBool arg.
// In some such cases, we can rewrite the CFG into a flatter form.
//
// (1) Look for a CFG of the form
//
//	p   other pred(s)
//	 \ /
//	  b
//	 / \
//	t   other succ
//
// in which b is an If block containing a single phi value with a single use (b's Control),
// which has a ConstBool arg.
// p is the predecessor corresponding to the argument slot in which the ConstBool is found.
// t is the successor corresponding to the value of the ConstBool arg.
//
// Rewrite this into
//
//	p   other pred(s)
//	|  /
//	| b
//	|/ \
//	t   u
//
// and remove the appropriate phi arg(s).
//
// (2) Look for a CFG of the form
//
//	p   q
//	 \ /
//	  b
//	 / \
//	t   u
//
// in which b is as described in (1).
// However, b may also contain other phi values.
// The CFG will be modified as described in (1).
// However, in order to handle those other phi values,
// for each other phi value w, we must be able to eliminate w from b.
// We can do that though a combination of moving w to a different block
// and rewriting uses of w to use a different value instead.
// See shortcircuitPhiPlan for details.
func shortcircuitBlock(b *Block) bool {
	if b.Kind != BlockIf {
		return false
	}
	// Look for control values of the form Copy(Not(Copy(Phi(const, ...)))).
	// Those must be the only values in the b, and they each must be used only by b.
	// Track the negations so that we can swap successors as needed later.
	ctl := b.Controls[0]
	nval := 1 // the control value
	var swap int64
	for ctl.Uses == 1 && ctl.Block == b && (ctl.Op == OpCopy || ctl.Op == OpNot) {
		if ctl.Op == OpNot {
			swap = 1 ^ swap
		}
		ctl = ctl.Args[0]
		nval++ // wrapper around control value
	}
	if ctl.Op != OpPhi || ctl.Block != b || ctl.Uses != 1 {
		return false
	}
	nOtherPhi := 0
	for _, w := range b.Values {
		if w.Op == OpPhi && w != ctl {
			nOtherPhi++
		}
	}
	if nOtherPhi > 0 && len(b.Preds) != 2 {
		// We rely on b having exactly two preds in shortcircuitPhiPlan
		// to reason about the values of phis.
		return false
	}
	if len(b.Values) != nval+nOtherPhi {
		return false
	}
	if nOtherPhi > 0 {
		// Check for any phi which is the argument of another phi.
		// These cases are tricky, as substitutions done by replaceUses
		// are no longer trivial to do in any ordering. See issue 45175.
		m := make(map[*Value]bool, 1+nOtherPhi)
		for _, v := range b.Values {
			if v.Op == OpPhi {
				m[v] = true
			}
		}
		for v := range m {
			for _, a := range v.Args {
				if a != v && m[a] {
					return false
				}
			}
		}
	}

// Locate index of first const phi arg.
	cidx := -1
	for i, a := range ctl.Args {
		if a.Op == OpConstBool {
			cidx = i
			break
		}
	}
	if cidx == -1 {
		return false
	}

// p is the predecessor corresponding to cidx.
	pe := b.Preds[cidx]
	p := pe.b
	pi := pe.i

// t is the "taken" branch: the successor we always go to when coming in from p.
	ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap
	te := b.Succs[ti]
	t := te.b
	if p == b || t == b {
		// This is an infinite loop; we can't remove it. See issue 33903.
		return false
	}

var fixPhi func(*Value, int)
	if nOtherPhi > 0 {
		fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti)
		if fixPhi == nil {
			return false
		}
	}

// We're committed. Update CFG and Phis.
	// If you modify this section, update shortcircuitPhiPlan corresponding.

// Remove b's incoming edge from p.
	b.removePred(cidx)
	b.removePhiArg(ctl, cidx)

// Redirect p's outgoing edge to t.
	p.Succs[pi] = Edge{t, len(t.Preds)}

// Fix up t to have one more predecessor.
	t.Preds = append(t.Preds, Edge{p, pi})
	for _, v := range t.Values {
		if v.Op != OpPhi {
			continue
		}
		v.AddArg(v.Args[te.i])
	}

if nOtherPhi != 0 {
		// Adjust all other phis as necessary.
		// Use a plain for loop instead of range because fixPhi may move phis,
		// thus modifying b.Values.
		for i := 0; i < len(b.Values); i++ {
			phi := b.Values[i]
			if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi {
				continue
			}
			fixPhi(phi, i)
			if phi.Block == b {
				continue
			}
			// phi got moved to a different block with v.moveTo.
			// Adjust phi values in this new block that refer
			// to phi to refer to the corresponding phi arg instead.
			// phi used to be evaluated prior to this block,
			// and now it is evaluated in this block.
			for _, v := range phi.Block.Values {
				if v.Op != OpPhi || v == phi {
					continue
				}
				for j, a := range v.Args {
					if a == phi {
						v.SetArg(j, phi.Args[j])
					}
				}
			}
			if phi.Uses != 0 {
				phielimValue(phi)
			} else {
				phi.reset(OpInvalid)
			}
			i-- // v.moveTo put a new value at index i; reprocess
		}

// We may have left behind some phi values with no uses
		// but the wrong number of arguments. Eliminate those.
		for _, v := range b.Values {
			if v.Uses == 0 {
				v.reset(OpInvalid)
			}
		}
	}

if len(b.Preds) == 0 {
		// Block is now dead.
		b.Kind = BlockInvalid
	}

phielimValue(ctl)
	return true
}

// shortcircuitPhiPlan returns a function to handle non-ctl phi values in b,
// where b is as described in shortcircuitBlock.
// The returned function accepts a value v
// and the index i of v in v.Block: v.Block.Values[i] == v.
// If the returned function moves v to a different block, it will use v.moveTo.
// cidx is the index in ctl of the ConstBool arg.
// ti is the index in b.Succs of the always taken branch when arriving from p.
// If shortcircuitPhiPlan returns nil, there is no plan available,
// and the CFG modifications must not proceed.
// The returned function assumes that shortcircuitBlock has completed its CFG modifications.
func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) {
	// t is the "taken" branch: the successor we always go to when coming in from p.
	t := b.Succs[ti].b
	// u is the "untaken" branch: the successor we never go to when coming in from p.
	u := b.Succs[1^ti].b

// In the following CFG matching, ensure that b's preds are entirely distinct from b's succs.
	// This is probably a stronger condition than required, but this happens extremely rarely,
	// and it makes it easier to avoid getting deceived by pretty ASCII charts. See #44465.
	if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u {
		return nil
	}

// Look for some common CFG structures
	// in which the outbound paths from b merge,
	// with no other preds joining them.
	// In these cases, we can reconstruct what the value
	// of any phi in b must be in the successor blocks.

if len(t.Preds) == 1 && len(t.Succs) == 1 &&
		len(u.Preds) == 1 && len(u.Succs) == 1 &&
		t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 {
		// p   q
		//  \ /
		//   b
		//  / \
		// t   u
		//  \ /
		//   m
		//
		// After the CFG modifications, this will look like
		//
		// p   q
		// |  /
		// | b
		// |/ \
		// t   u
		//  \ /
		//   m
		//
		// NB: t.Preds is (b, p), not (p, b).
		m := t.Succs[0].b
		return func(v *Value, i int) {
			// Replace any uses of v in t and u with the value v must have,
			// given that we have arrived at that block.
			// Then move v to m and adjust its value accordingly;
			// this handles all other uses of v.
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(m, i)
			// The phi in m belongs to whichever pred idx corresponds to t.
			if m.Preds[0].b == t {
				v.SetArgs2(phi, argQ)
			} else {
				v.SetArgs2(argQ, phi)
			}
		}
	}

if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t {
		// p   q
		//  \ /
		//   b
		//   |\
		//   | u
		//   |/
		//   t
		//
		// After the CFG modifications, this will look like
		//
		//     q
		//    /
		//   b
		//   |\
		// p | u
		//  \|/
		//   t
		//
		// NB: t.Preds is (b or u, b or u, p).
		return func(v *Value, i int) {
			// Replace any uses of v in u. Then move v to t.
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			v.moveTo(t, i)
			v.SetArgs3(argQ, argQ, argP)
		}
	}

if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u {
		// p   q
		//  \ /
		//   b
		//  /|
		// t |
		//  \|
		//   u
		//
		// After the CFG modifications, this will look like
		//
		// p   q
		// |  /
		// | b
		// |/|
		// t |
		//  \|
		//   u
		//
		// NB: t.Preds is (b, p), not (p, b).
		return func(v *Value, i int) {
			// Replace any uses of v in t. Then move v to u.
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(u, i)
			v.SetArgs2(argQ, phi)
		}
	}

// Look for some common CFG structures
	// in which one outbound path from b exits,
	// with no other preds joining.
	// In these cases, we can reconstruct what the value
	// of any phi in b must be in the path leading to exit,
	// and move the phi to the non-exit path.

if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 {
		// p   q
		//  \ /
		//   b
		//  / \
		// t   u
		//
		// where t is an Exit/Ret block.
		//
		// After the CFG modifications, this will look like
		//
		// p   q
		// |  /
		// | b
		// |/ \
		// t   u
		//
		// NB: t.Preds is (b, p), not (p, b).
		return func(v *Value, i int) {
			// Replace any uses of v in t and x. Then move v to u.
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			// If there are no uses of v in t or x, this phi will be unused.
			// That's OK; it's not worth the cost to prevent that.
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(u, i)
			v.SetArgs1(argQ)
		}
	}

if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 {
		// p   q
		//  \ /
		//   b
		//  / \
		// t   u
		//
		// where u is an Exit/Ret block.
		//
		// After the CFG modifications, this will look like
		//
		// p   q
		// |  /
		// | b
		// |/ \
		// t   u
		//
		// NB: t.Preds is (b, p), not (p, b).
		return func(v *Value, i int) {
			// Replace any uses of v in u (and x). Then move v to t.
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			v.moveTo(t, i)
			v.SetArgs2(argQ, argP)
		}
	}

// TODO: handle more cases; shortcircuit optimizations turn out to be reasonably high impact
	return nil
}

// replaceUses replaces all uses of old in b with new.
func (b *Block) replaceUses(old, new *Value) {
	for _, v := range b.Values {
		for i, a := range v.Args {
			if a == old {
				v.SetArg(i, new)
			}
		}
	}
	for i, v := range b.ControlValues() {
		if v == old {
			b.ReplaceControl(i, new)
		}
	}
}

// moveTo moves v to dst, adjusting the appropriate Block.Values slices.
// The caller is responsible for ensuring that this is safe.
// i is the index of v in v.Block.Values.
func (v *Value) moveTo(dst *Block, i int) {
	if dst.Func.scheduled {
		v.Fatalf("moveTo after scheduling")
	}
	src := v.Block
	if src.Values[i] != v {
		v.Fatalf("moveTo bad index %d", v, i)
	}
	if src == dst {
		return
	}
	v.Block = dst
	dst.Values = append(dst.Values, v)
	last := len(src.Values) - 1
	src.Values[i] = src.Values[last]
	src.Values[last] = nil
	src.Values = src.Values[:last]
}

X7ROOT File Manager

Editing: shortcircuit.go

Upload File

Create Folder