Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: inline devirtualized functions if they are inlineable #60032

Closed
silbinarywolf opened this issue May 7, 2023 · 2 comments
Closed
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@silbinarywolf
Copy link
Contributor

silbinarywolf commented May 7, 2023

What version of Go are you using (go version)?

go version devel go1.21-3e35df5edb Fri May 5 23:33:02 2023 +0000 windows/amd64

What did you do?

I wrote a function that takes an interface and calls a method on it. I knew that it would be devirtualized and call MyStruct.Do directly, however I also expected the call to MyStruct.Do to also be inlined if it's inlineable after the fact. But due to inlining happening before devirtualization, that doesn't happen.

So, I'm proposing that after we devirtualize interface method calls that we also see at that point in time if the devirtualized method can be inlined.

package main

type Doer interface {
	Do()
}

type MyStruct struct {
}

func (*MyStruct) Do() {
	panic("Hey it works")
}

func Do(do Doer) {
	do.Do()
}

func main() {
	s := new(MyStruct)
	Do(s)
}

What did you expect to see?

When running go build && go tool objdump test.exe > test.sout on the code above, I expected something more like this, where the there would be no CALL to MyStruct.Do

TEXT main.main(SB) D:/GoProjects/proposal-devirt-inline/devirt-inline.go
  devirt-inline.go:18	0x45afa0		493b6610		CMPQ 0x10(R14), SP				
  devirt-inline.go:18	0x45afa4		7620			JBE 0x45afc6					
  devirt-inline.go:18	0x45afa6		55			PUSHQ BP					
  devirt-inline.go:18	0x45afa7		4889e5			MOVQ SP, BP					
  devirt-inline.go:18	0x45afaa		4883ec10		SUBQ $0x10, SP					
  devirt-inline.go:20	0x45afae		90			NOPL						
  devirt-inline.go:15	0x45afaf		90			NOPL						
  devirt-inline.go:11	0x45afb0		488d05c9460000		LEAQ runtime.types+18048(SB), AX		
  devirt-inline.go:11	0x45afb7		488d1d625c0200		LEAQ runtime.godebugDefault.str+16(SB), BX	
  devirt-inline.go:11	0x45afbe		6690			NOPW						
  devirt-inline.go:11	0x45afc0		e83b2efdff		CALL runtime.gopanic(SB)			
  devirt-inline.go:11	0x45afc5		90			NOPL						
  devirt-inline.go:18	0x45afc6		e8758dffff		CALL runtime.morestack_noctxt.abi0(SB)		
  devirt-inline.go:18	0x45afcb		ebd3			JMP main.main(SB)				
		

What did you see instead?

When running go build && go tool objdump test.exe > test.sout, I instead see the following.

TEXT main.(*MyStruct).Do(SB) D:/GoProjects/proposal-devirt-inline/devirt-inline.go
  devirt-inline.go:10	0x45afa0		493b6610		CMPQ 0x10(R14), SP				
  devirt-inline.go:10	0x45afa4		7620			JBE 0x45afc6					
  devirt-inline.go:10	0x45afa6		55			PUSHQ BP					
  devirt-inline.go:10	0x45afa7		4889e5			MOVQ SP, BP					
  devirt-inline.go:10	0x45afaa		4883ec10		SUBQ $0x10, SP					
  devirt-inline.go:11	0x45afae		488d05cb560000		LEAQ type:*+18048(SB), AX			
  devirt-inline.go:11	0x45afb5		488d1d546c0200		LEAQ runtime.godebugDefault.str+16(SB), BX	
  devirt-inline.go:11	0x45afbc		0f1f4000		NOPL 0(AX)					
  devirt-inline.go:11	0x45afc0		e83b2efdff		CALL runtime.gopanic(SB)			
  devirt-inline.go:11	0x45afc5		90			NOPL						
  devirt-inline.go:10	0x45afc6		e8758dffff		CALL runtime.morestack_noctxt.abi0(SB)		
  devirt-inline.go:10	0x45afcb		ebd3			JMP main.(*MyStruct).Do(SB)	

TEXT main.main(SB) D:/GoProjects/proposal-devirt-inline/devirt-inline.go
  devirt-inline.go:18	0x45afe0		493b6610		CMPQ 0x10(R14), SP			
  devirt-inline.go:18	0x45afe4		7619			JBE 0x45afff				
  devirt-inline.go:18	0x45afe6		55			PUSHQ BP				
  devirt-inline.go:18	0x45afe7		4889e5			MOVQ SP, BP				
  devirt-inline.go:18	0x45afea		4883ec08		SUBQ $0x8, SP				
  devirt-inline.go:20	0x45afee		90			NOPL					
  devirt-inline.go:15	0x45afef		488d442408		LEAQ 0x8(SP), AX			
  devirt-inline.go:15	0x45aff4		e8a7ffffff		CALL main.(*MyStruct).Do(SB)		
  devirt-inline.go:21	0x45aff9		4883c408		ADDQ $0x8, SP				
  devirt-inline.go:21	0x45affd		5d			POPQ BP					
  devirt-inline.go:21	0x45affe		c3			RET					
  devirt-inline.go:18	0x45afff		90			NOPL					
  devirt-inline.go:18	0x45b000		e83b8dffff		CALL runtime.morestack_noctxt.abi0(SB)	
  devirt-inline.go:18	0x45b005		ebd9			JMP main.main(SB)				

Proposed solution

I can formerly put the following into a PR/CL but the gist of what I propose is:

  • During devirtualization, we simply check if the devirtualized function call allows inlining and has Func.Inl set.
  • If it does, inline the call.

I'm not sure if this particular solution is viable however as I haven't benchmarked anything as of yet but this at least proves it can be done.

The following changes to src\cmd\compile\internal\devirtualize\devirtualize.go are how I got the assembly output for the "What did you expect to see" section above.

package devirtualize

import (
	"cmd/compile/internal/base"
	"cmd/compile/internal/inline"
	"cmd/compile/internal/ir"
	"cmd/compile/internal/typecheck"
	"cmd/compile/internal/types"
	"cmd/internal/obj"
)

// Func devirtualizes calls within fn where possible.
func Func(fn *ir.Func) {
	ir.CurFunc = fn

	// For promoted methods (including value-receiver methods promoted to pointer-receivers),
	// the interface method wrapper may contain expressions that can panic (e.g., ODEREF, ODOTPTR, ODOTINTER).
	// Devirtualization involves inlining these expressions (and possible panics) to the call site.
	// This normally isn't a problem, but for go/defer statements it can move the panic from when/where
	// the call executes to the go/defer statement itself, which is a visible change in semantics (e.g., #52072).
	// To prevent this, we skip devirtualizing calls within go/defer statements altogether.
	goDeferCall := make(map[*ir.CallExpr]bool)
	var edit func(n ir.Node) ir.Node
	edit = func(n ir.Node) ir.Node {
		switch n := n.(type) {
		case *ir.GoDeferStmt:
			if call, ok := n.Call.(*ir.CallExpr); ok {
				goDeferCall[call] = true
			}
		case *ir.CallExpr:
			if !goDeferCall[n] {
				if inlCall := Call(n); inlCall != nil {
					return inlCall
				}
			}
		}
		ir.EditChildren(n, edit)
		return n
	}
	ir.EditChildren(fn, edit)
}

// Call devirtualizes the given call if possible.
func Call(call *ir.CallExpr) *ir.InlinedCallExpr {
	if call.Op() != ir.OCALLINTER {
		return nil
	}
	sel := call.X.(*ir.SelectorExpr)
	r := ir.StaticValue(sel.X)
	if r.Op() != ir.OCONVIFACE {
		return nil
	}
	recv := r.(*ir.ConvExpr)

	typ := recv.X.Type()
	if typ.IsInterface() {
		return nil
	}

	// If typ is a shape type, then it was a type argument originally
	// and we'd need an indirect call through the dictionary anyway.
	// We're unable to devirtualize this call.
	if typ.IsShape() {
		return nil
	}

	// If typ *has* a shape type, then it's an shaped, instantiated
	// type like T[go.shape.int], and its methods (may) have an extra
	// dictionary parameter. We could devirtualize this call if we
	// could derive an appropriate dictionary argument.
	//
	// TODO(mdempsky): If typ has has a promoted non-generic method,
	// then that method won't require a dictionary argument. We could
	// still devirtualize those calls.
	//
	// TODO(mdempsky): We have the *runtime.itab in recv.TypeWord. It
	// should be possible to compute the represented type's runtime
	// dictionary from this (e.g., by adding a pointer from T[int]'s
	// *runtime._type to .dict.T[int]; or by recognizing static
	// references to go:itab.T[int],iface and constructing a direct
	// reference to .dict.T[int]).
	if typ.HasShape() {
		if base.Flag.LowerM != 0 {
			base.WarnfAt(call.Pos(), "cannot devirtualize %v: shaped receiver %v", call, typ)
		}
		return nil
	}

	// Further, if sel.X's type has a shape type, then it's a shaped
	// interface type. In this case, the (non-dynamic) TypeAssertExpr
	// we construct below would attempt to create an itab
	// corresponding to this shaped interface type; but the actual
	// itab pointer in the interface value will correspond to the
	// original (non-shaped) interface type instead. These are
	// functionally equivalent, but they have distinct pointer
	// identities, which leads to the type assertion failing.
	//
	// TODO(mdempsky): We know the type assertion here is safe, so we
	// could instead set a flag so that walk skips the itab check. For
	// now, punting is easy and safe.
	if sel.X.Type().HasShape() {
		if base.Flag.LowerM != 0 {
			base.WarnfAt(call.Pos(), "cannot devirtualize %v: shaped interface %v", call, sel.X.Type())
		}
		return nil
	}

	dt := ir.NewTypeAssertExpr(sel.Pos(), sel.X, nil)
	dt.SetType(typ)
	x := typecheck.Callee(ir.NewSelectorExpr(sel.Pos(), ir.OXDOT, dt, sel.Sel))
	switch x.Op() {
	case ir.ODOTMETH:
		x := x.(*ir.SelectorExpr)
		if base.Flag.LowerM != 0 {
			base.WarnfAt(call.Pos(), "devirtualizing %v to %v", sel, typ)
		}
		call.SetOp(ir.OCALLMETH)
		call.X = x
	case ir.ODOTINTER:
		// Promoted method from embedded interface-typed field (#42279).
		x := x.(*ir.SelectorExpr)
		if base.Flag.LowerM != 0 {
			base.WarnfAt(call.Pos(), "partially devirtualizing %v to %v", sel, typ)
		}
		call.SetOp(ir.OCALLINTER)
		call.X = x
	default:
		// TODO(mdempsky): Turn back into Fatalf after more testing.
		if base.Flag.LowerM != 0 {
			base.WarnfAt(call.Pos(), "failed to devirtualize %v (%v)", x, x.Op())
		}
		return nil
	}

	// Duplicated logic from typecheck for function call return
	// value types.
	//
	// Receiver parameter size may have changed; need to update
	// call.Type to get correct stack offsets for result
	// parameters.
	types.CheckSize(x.Type())
	switch ft := x.Type(); ft.NumResults() {
	case 0:
	case 1:
		call.SetType(ft.Results().Field(0).Type)
	default:
		call.SetType(ft.Results())
	}

	// Desugar OCALLMETH, if we created one (#57309).
	typecheck.FixMethodCall(call)

	// Inline devirtualized function if inlineable (#60032).
	if call.Op() == ir.OCALLFUNC && !call.NoInline {
		v := ir.StaticValue(call.X)
		if v.Op() != ir.OMETHEXPR {
			base.FatalfAt(call.Pos(), "expected call to be OMETHEXPR")
		}
		name := ir.MethodExprName(v)

		// If function has Inl not nil, then in the previous inline phase
		// it was deemed as inlineable.
		if name != nil && name.Func != nil && name.Func.Inl != nil {
			fn := name.Func
			parent := base.Ctxt.PosTable.Pos(call.Pos()).Base().InliningIndex()
			sym := fn.Linksym()
			inlIndex := base.Ctxt.InlTree.Add(parent, call.Pos(), sym)
			if inlinedCallExpr := inline.InlineCall(call, fn, inlIndex); inlinedCallExpr != nil {
				// Generate to avoid bugs like:
				// - AbsFuncDwarfSym requested for encoding/binary.bigEndian.Uint64, not seen during inlining
				if base.Flag.GenDwarfInl > 0 {
					if !sym.WasInlined() {
						base.Ctxt.DwFixups.SetPrecursorFunc(sym, fn)
						sym.Set(obj.AttrWasInlined, true)
					}
				}

				if base.Flag.LowerM != 0 {
					base.WarnfAt(call.Pos(), "inlining devirtualized call %v", name)
				}
				return inlinedCallExpr
			}
		}
	}

	return nil
}
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label May 7, 2023
@silbinarywolf silbinarywolf changed the title cmd/compile: inline devirtualized functions if inlineable cmd/compile: inline devirtualized functions if they are inlineable May 7, 2023
@cherrymui cherrymui added this to the Backlog milestone May 8, 2023
@cherrymui
Copy link
Member

cc @mdempsky @thanm @golang/compiler

@cherrymui cherrymui added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label May 8, 2023
@cherrymui
Copy link
Member

See also #52193 and #38992 . Closing as a dup. Thanks.

@cherrymui cherrymui closed this as not planned Won't fix, can't repro, duplicate, stale May 8, 2023
@golang golang locked and limited conversation to collaborators May 7, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

4 participants