src/cmd/compile/internal/ssacompile/tighten.go - go - Git at Google

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

 import (
 	"cmd/compile/internal/base"
 	"cmd/compile/internal/ssa"
 	"cmd/compile/internal/ssa/ssaop"
 )

 // tighten moves Values closer to the Blocks in which they are used.
 // This can reduce the amount of register spilling required,
 // if it doesn't also create more live values.
 // A Value can be moved to any block that
 // dominates all blocks in which it is used.
 func tighten(f *ssa.Func) {
 	if base.Flag.N != 0 && len(f.Blocks) < 10000 {
 		// Skip the optimization in -N mode, except for huge functions.
 		// Too many values live across blocks can cause pathological
 		// behavior in the register allocator (see issue 52180).
 		return
 	}

 	canMove := f.Cache.AllocBoolSlice(f.NumValues())
 	defer f.Cache.FreeBoolSlice(canMove)

 	// Compute the memory states of each block.
 	startMem := f.Cache.AllocValueSlice(f.NumBlocks())
 	defer f.Cache.FreeValueSlice(startMem)
 	endMem := f.Cache.AllocValueSlice(f.NumBlocks())
 	defer f.Cache.FreeValueSlice(endMem)
 	distinctArgs := f.NewSparseSet(f.NumValues())
 	defer f.RetSparseSet(distinctArgs)
 	memState(f, startMem, endMem)

 	for _, b := range f.Blocks {
 		for _, v := range b.Values {
 			if v.Op.IsLoweredGetClosurePtr() {
 				// Must stay in the entry block.
 				continue
 			}
 			switch v.Op {
 			case ssaop.OpPhi, ssaop.OpArg, ssaop.OpArgIntReg, ssaop.OpArgFloatReg, ssaop.OpSelect0, ssaop.OpSelect1, ssaop.OpSelectN:
 				// Phis need to stay in their block.
 				// Arg must stay in the entry block.
 				// Tuple selectors must stay with the tuple generator.
 				// SelectN is typically, ultimately, a register.
 				continue
 			}
 			if ssaop.OpcodeTable[v.Op].NilCheck {
 				// Nil checks need to stay in their block. See issue 72860.
 				continue
 			}
 			// Count distinct arguments which will need a register.
 			distinctArgs.Clear()

 			for _, a := range v.Args {
 				// SP and SB are special registers and have no effect on
 				// the allocation of general-purpose registers.
 				if a.NeedRegister() && a.Op != ssaop.OpSB && a.Op != ssaop.OpSP {
 					distinctArgs.Add(a.ID)
 				}
 			}

 			if distinctArgs.Size() >= 2 && !v.Type.IsFlags() {
 				// Don't move values with more than one input, as that may
 				// increase register pressure.
 				// We make an exception for flags, as we want flag generators
 				// moved next to uses (because we only have 1 flag register).
 				continue
 			}
 			canMove[v.ID] = true
 		}
 	}

 	// Build data structure for fast least-common-ancestor queries.
 	lca := makeLCArange(f)

 	// For each moveable value, record the block that dominates all uses found so far.
 	target := f.Cache.AllocBlockSlice(f.NumValues())
 	defer f.Cache.FreeBlockSlice(target)

 	// Grab loop information.
 	// We use this to make sure we don't tighten a value into a (deeper) loop.
 	idom := f.Idom()
 	loops := f.Loopnest()

 	changed := true
 	for changed {
 		changed = false

 		// Reset target
 		clear(target)

 		// Compute target locations (for moveable values only).
 		// target location = the least common ancestor of all uses in the dominator tree.
 		for _, b := range f.Blocks {
 			for _, v := range b.Values {
 				for i, a := range v.Args {
 					if !canMove[a.ID] {
 						continue
 					}
 					use := b
 					if v.Op == ssaop.OpPhi {
 						use = b.Preds[i].B
 					}
 					if target[a.ID] == nil {
 						target[a.ID] = use
 					} else {
 						target[a.ID] = lca.find(target[a.ID], use)
 					}
 				}
 			}
 			for _, c := range b.ControlValues() {
 				if !canMove[c.ID] {
 					continue
 				}
 				if target[c.ID] == nil {
 					target[c.ID] = b
 				} else {
 					target[c.ID] = lca.find(target[c.ID], b)
 				}
 			}
 		}

 		// If the target location is inside a loop,
 		// move the target location up to just before the loop head.
 		if !loops.HasIrreducible {
 			// Loop info might not be correct for irreducible loops. See issue 75569.
 			for _, b := range f.Blocks {
 				origloop := loops.B2L[b.ID]
 				for _, v := range b.Values {
 					t := target[v.ID]
 					if t == nil {
 						continue
 					}
 					targetloop := loops.B2L[t.ID]
 					for targetloop != nil && (origloop == nil || targetloop.Depth > origloop.Depth) {
 						t = idom[targetloop.Header.ID]
 						target[v.ID] = t
 						targetloop = loops.B2L[t.ID]
 					}
 				}
 			}
 		}

 		// Move values to target locations.
 		for _, b := range f.Blocks {
 			for i := 0; i < len(b.Values); i++ {
 				v := b.Values[i]
 				t := target[v.ID]
 				if t == nil || t == b {
 					// v is not moveable, or is already in correct place.
 					continue
 				}
 				if mem := v.MemoryArg(); mem != nil {
 					if startMem[t.ID] != mem {
 						// We can't move a value with a memory arg unless the target block
 						// has that memory arg as its starting memory.
 						continue
 					}
 				}
 				if f.Pass.Debug > 0 {
 					b.Func.Warnl(v.Pos, "%v is moved", v.Op)
 				}
 				// Move v to the block which dominates its uses.
 				t.Values = append(t.Values, v)
 				v.Block = t
 				last := len(b.Values) - 1
 				b.Values[i] = b.Values[last]
 				b.Values[last] = nil
 				b.Values = b.Values[:last]
 				changed = true
 				i--
 			}
 		}
 	}
 }

 // phiTighten moves constants closer to phi users.
 // This pass avoids having lots of constants live for lots of the program.
 // See issue 16407.
 func phiTighten(f *ssa.Func) {
 	for _, b := range f.Blocks {
 		for _, v := range b.Values {
 			if v.Op != ssaop.OpPhi {
 				continue
 			}
 			for i, a := range v.Args {
 				if !a.Rematerializeable() {
 					continue // not a constant we can move around
 				}
 				if a.Block == b.Preds[i].B {
 					continue // already in the right place
 				}
 				// Make a copy of a, put in predecessor block.
 				v.SetArg(i, a.CopyInto(b.Preds[i].B))
 			}
 		}
 	}
 }

 // memState computes the memory state at the beginning and end of each block of
 // the function. The memory state is represented by a value of mem type.
 // The returned result is stored in startMem and endMem, and endMem is nil for
 // blocks with no successors (Exit,Ret,RetJmp blocks). This algorithm is not
 // suitable for infinite loop blocks that do not contain any mem operations.
 // For example:
 // b1:
 //
 //	(some values)
 //
 // plain -> b2
 // b2: <- b1 b2
 // Plain -> b2
 //
 // Algorithm introduction:
 //  1. The start memory state of a block is InitMem, a Phi node of type mem or
 //     an incoming memory value.
 //  2. The start memory state of a block is consistent with the end memory state
 //     of its parent nodes. If the start memory state of a block is a Phi value,
 //     then the end memory state of its parent nodes is consistent with the
 //     corresponding argument value of the Phi node.
 //  3. The algorithm first obtains the memory state of some blocks in the tree
 //     in the first step. Then floods the known memory state to other nodes in
 //     the second step.
 func memState(f *ssa.Func, startMem, endMem []*ssa.Value) {
 	// This slice contains the set of blocks that have had their startMem set but this
 	// startMem value has not yet been propagated to the endMem of its predecessors
 	changed := make([]*ssa.Block, 0)
 	// First step, init the memory state of some blocks.
 	for _, b := range f.Blocks {
 		for _, v := range b.Values {
 			var mem *ssa.Value
 			if v.Op == ssaop.OpPhi {
 				if v.Type.IsMemory() {
 					mem = v
 				}
 			} else if v.Op == ssaop.OpInitMem {
 				mem = v // This is actually not needed.
 			} else if a := v.MemoryArg(); a != nil && a.Block != b {
 				// The only incoming memory value doesn't belong to this block.
 				mem = a
 			}
 			if mem != nil {
 				if old := startMem[b.ID]; old != nil {
 					if old == mem {
 						continue
 					}
 					f.Fatalf("func %s, startMem[%v] has different values, old %v, new %v", f.Name, b, old, mem)
 				}
 				startMem[b.ID] = mem
 				changed = append(changed, b)
 			}
 		}
 	}

 	// Second step, floods the known memory state of some blocks to others.
 	for len(changed) != 0 {
 		top := changed[0]
 		changed = changed[1:]
 		mem := startMem[top.ID]
 		for i, p := range top.Preds {
 			pb := p.B
 			if endMem[pb.ID] != nil {
 				continue
 			}
 			if mem.Op == ssaop.OpPhi && mem.Block == top {
 				endMem[pb.ID] = mem.Args[i]
 			} else {
 				endMem[pb.ID] = mem
 			}
 			if startMem[pb.ID] == nil {
 				startMem[pb.ID] = endMem[pb.ID]
 				changed = append(changed, pb)
 			}
 		}
 	}
 }
	// 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 ssacompile

	import (
	"cmd/compile/internal/base"
	"cmd/compile/internal/ssa"
	"cmd/compile/internal/ssa/ssaop"
	)

	// tighten moves Values closer to the Blocks in which they are used.
	// This can reduce the amount of register spilling required,
	// if it doesn't also create more live values.
	// A Value can be moved to any block that
	// dominates all blocks in which it is used.
	func tighten(f *ssa.Func) {
	if base.Flag.N != 0 && len(f.Blocks) < 10000 {
	// Skip the optimization in -N mode, except for huge functions.
	// Too many values live across blocks can cause pathological
	// behavior in the register allocator (see issue 52180).
	return
	}

	canMove := f.Cache.AllocBoolSlice(f.NumValues())
	defer f.Cache.FreeBoolSlice(canMove)

	// Compute the memory states of each block.
	startMem := f.Cache.AllocValueSlice(f.NumBlocks())
	defer f.Cache.FreeValueSlice(startMem)
	endMem := f.Cache.AllocValueSlice(f.NumBlocks())
	defer f.Cache.FreeValueSlice(endMem)
	distinctArgs := f.NewSparseSet(f.NumValues())
	defer f.RetSparseSet(distinctArgs)
	memState(f, startMem, endMem)

	for _, b := range f.Blocks {
	for _, v := range b.Values {
	if v.Op.IsLoweredGetClosurePtr() {
	// Must stay in the entry block.
	continue
	}
	switch v.Op {
	case ssaop.OpPhi, ssaop.OpArg, ssaop.OpArgIntReg, ssaop.OpArgFloatReg, ssaop.OpSelect0, ssaop.OpSelect1, ssaop.OpSelectN:
	// Phis need to stay in their block.
	// Arg must stay in the entry block.
	// Tuple selectors must stay with the tuple generator.
	// SelectN is typically, ultimately, a register.
	continue
	}
	if ssaop.OpcodeTable[v.Op].NilCheck {
	// Nil checks need to stay in their block. See issue 72860.
	continue
	}
	// Count distinct arguments which will need a register.
	distinctArgs.Clear()

	for _, a := range v.Args {
	// SP and SB are special registers and have no effect on
	// the allocation of general-purpose registers.
	if a.NeedRegister() && a.Op != ssaop.OpSB && a.Op != ssaop.OpSP {
	distinctArgs.Add(a.ID)
	}
	}

	if distinctArgs.Size() >= 2 && !v.Type.IsFlags() {
	// Don't move values with more than one input, as that may
	// increase register pressure.
	// We make an exception for flags, as we want flag generators
	// moved next to uses (because we only have 1 flag register).
	continue
	}
	canMove[v.ID] = true
	}
	}

	// Build data structure for fast least-common-ancestor queries.
	lca := makeLCArange(f)

	// For each moveable value, record the block that dominates all uses found so far.
	target := f.Cache.AllocBlockSlice(f.NumValues())
	defer f.Cache.FreeBlockSlice(target)

	// Grab loop information.
	// We use this to make sure we don't tighten a value into a (deeper) loop.
	idom := f.Idom()
	loops := f.Loopnest()

	changed := true
	for changed {
	changed = false

	// Reset target
	clear(target)

	// Compute target locations (for moveable values only).
	// target location = the least common ancestor of all uses in the dominator tree.
	for _, b := range f.Blocks {
	for _, v := range b.Values {
	for i, a := range v.Args {
	if !canMove[a.ID] {
	continue
	}
	use := b
	if v.Op == ssaop.OpPhi {
	use = b.Preds[i].B
	}
	if target[a.ID] == nil {
	target[a.ID] = use
	} else {
	target[a.ID] = lca.find(target[a.ID], use)
	}
	}
	}
	for _, c := range b.ControlValues() {
	if !canMove[c.ID] {
	continue
	}
	if target[c.ID] == nil {
	target[c.ID] = b
	} else {
	target[c.ID] = lca.find(target[c.ID], b)
	}
	}
	}

	// If the target location is inside a loop,
	// move the target location up to just before the loop head.
	if !loops.HasIrreducible {
	// Loop info might not be correct for irreducible loops. See issue 75569.
	for _, b := range f.Blocks {
	origloop := loops.B2L[b.ID]
	for _, v := range b.Values {
	t := target[v.ID]
	if t == nil {
	continue
	}
	targetloop := loops.B2L[t.ID]
	for targetloop != nil && (origloop == nil \|\| targetloop.Depth > origloop.Depth) {
	t = idom[targetloop.Header.ID]
	target[v.ID] = t
	targetloop = loops.B2L[t.ID]
	}
	}
	}
	}

	// Move values to target locations.
	for _, b := range f.Blocks {
	for i := 0; i < len(b.Values); i++ {
	v := b.Values[i]
	t := target[v.ID]
	if t == nil \|\| t == b {
	// v is not moveable, or is already in correct place.
	continue
	}
	if mem := v.MemoryArg(); mem != nil {
	if startMem[t.ID] != mem {
	// We can't move a value with a memory arg unless the target block
	// has that memory arg as its starting memory.
	continue
	}
	}
	if f.Pass.Debug > 0 {
	b.Func.Warnl(v.Pos, "%v is moved", v.Op)
	}
	// Move v to the block which dominates its uses.
	t.Values = append(t.Values, v)
	v.Block = t
	last := len(b.Values) - 1
	b.Values[i] = b.Values[last]
	b.Values[last] = nil
	b.Values = b.Values[:last]
	changed = true
	i--
	}
	}
	}
	}

	// phiTighten moves constants closer to phi users.
	// This pass avoids having lots of constants live for lots of the program.
	// See issue 16407.
	func phiTighten(f *ssa.Func) {
	for _, b := range f.Blocks {
	for _, v := range b.Values {
	if v.Op != ssaop.OpPhi {
	continue
	}
	for i, a := range v.Args {
	if !a.Rematerializeable() {
	continue // not a constant we can move around
	}
	if a.Block == b.Preds[i].B {
	continue // already in the right place
	}
	// Make a copy of a, put in predecessor block.
	v.SetArg(i, a.CopyInto(b.Preds[i].B))
	}
	}
	}
	}

	// memState computes the memory state at the beginning and end of each block of
	// the function. The memory state is represented by a value of mem type.
	// The returned result is stored in startMem and endMem, and endMem is nil for
	// blocks with no successors (Exit,Ret,RetJmp blocks). This algorithm is not
	// suitable for infinite loop blocks that do not contain any mem operations.
	// For example:
	// b1:
	//
	// (some values)
	//
	// plain -> b2
	// b2: <- b1 b2
	// Plain -> b2
	//
	// Algorithm introduction:
	// 1. The start memory state of a block is InitMem, a Phi node of type mem or
	// an incoming memory value.
	// 2. The start memory state of a block is consistent with the end memory state
	// of its parent nodes. If the start memory state of a block is a Phi value,
	// then the end memory state of its parent nodes is consistent with the
	// corresponding argument value of the Phi node.
	// 3. The algorithm first obtains the memory state of some blocks in the tree
	// in the first step. Then floods the known memory state to other nodes in
	// the second step.
	func memState(f ssa.Func, startMem, endMem []ssa.Value) {
	// This slice contains the set of blocks that have had their startMem set but this
	// startMem value has not yet been propagated to the endMem of its predecessors
	changed := make([]*ssa.Block, 0)
	// First step, init the memory state of some blocks.
	for _, b := range f.Blocks {
	for _, v := range b.Values {
	var mem *ssa.Value
	if v.Op == ssaop.OpPhi {
	if v.Type.IsMemory() {
	mem = v
	}
	} else if v.Op == ssaop.OpInitMem {
	mem = v // This is actually not needed.
	} else if a := v.MemoryArg(); a != nil && a.Block != b {
	// The only incoming memory value doesn't belong to this block.
	mem = a
	}
	if mem != nil {
	if old := startMem[b.ID]; old != nil {
	if old == mem {
	continue
	}
	f.Fatalf("func %s, startMem[%v] has different values, old %v, new %v", f.Name, b, old, mem)
	}
	startMem[b.ID] = mem
	changed = append(changed, b)
	}
	}
	}

	// Second step, floods the known memory state of some blocks to others.
	for len(changed) != 0 {
	top := changed[0]
	changed = changed[1:]
	mem := startMem[top.ID]
	for i, p := range top.Preds {
	pb := p.B
	if endMem[pb.ID] != nil {
	continue
	}
	if mem.Op == ssaop.OpPhi && mem.Block == top {
	endMem[pb.ID] = mem.Args[i]
	} else {
	endMem[pb.ID] = mem
	}
	if startMem[pb.ID] == nil {
	startMem[pb.ID] = endMem[pb.ID]
	changed = append(changed, pb)
	}
	}
	}
	}