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: OpInlMark can get removed by SSA dead code elimination, resulting in invalid inlining trees #54625

Open
mdempsky opened this issue Aug 23, 2022 · 19 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. help wanted NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@mdempsky
Copy link
Member

mdempsky commented Aug 23, 2022

See discussion at #46234.

The immediate issue is that https://go.dev/play/p/OikFLBmKguY?v=gotip causes the loop at

to never terminate, because the inlining "tree" has cycles.

The bigger issue is that we're generating trees like this for kube-apiserver, and this is presumably the root cause of #54593.

@mdempsky mdempsky added the NeedsFix The path to resolution is known, but the work has not been done. label Aug 23, 2022
@mdempsky mdempsky added this to the Go1.20 milestone Aug 23, 2022
@mdempsky mdempsky self-assigned this Aug 23, 2022
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Aug 23, 2022
@mdempsky
Copy link
Member Author

GOEXPERIMENT=nounified go build -gcflags=-d=pctab=pctoinline net/http produces:

funcpctab net/http.readTransfer [valfunc=pctoinline]
...
    7b      3 00123 (/usr/lib/google-golang/src/net/http/transfer.go:563)       MOVQ    CX, net/http.r+216(SP)
...
-- inlining tree for net/http.readTransfer:
0 | -1 | net/http/internal.NewChunkedReader (/usr/lib/google-golang/src/net/http/transfer.go:563:49) pc=1000
1 | 0 | bufio.NewReader ($GOROOT/src/net/http/internal/chunked.go:32:23) pc=0
2 | 1 | bufio.NewReaderSize ($GOROOT/src/bufio/bufio.go:63:22) pc=0
3 | 2 | bufio.(*Reader).reset ($GOROOT/src/bufio/bufio.go:57:9) pc=0
4 | -1 | io.LimitReader (/usr/lib/google-golang/src/net/http/transfer.go:568:37) pc=1472
5 | -1 | net/http.Header.get (/usr/lib/google-golang/src/net/http/transfer.go:530:47) pc=573
6 | -1 | net/http.bodyAllowedForStatus (/usr/lib/google-golang/src/net/http/transfer.go:550:60) pc=746
7 | -1 | net/http.noResponseBodyExpected (/usr/lib/google-golang/src/net/http/transfer.go:560:28) pc=845
8 | -1 | net/http.bodyAllowedForStatus (/usr/lib/google-golang/src/net/http/transfer.go:560:70) pc=845
--

Note the pc=0 value on entries 1 through 3, and that entry 3 is actually referenced by the MOVQ instruction.

The consequence of this is that when unwinding the stack at the MOVQ instruction, we'll find the bufio.(*Reader).reset call, but treat it as called directly by readTransfer, rather than transitively inlined via internal.NewChunkedReader->bufio.NewReader->bufio.NewReaderSize->bufio.(*Reader).reset.

@mdempsky
Copy link
Member Author

Interestingly, that's the only function that ends up with a corrupt inline tree with GOEXPERIMENT=nounified that I could find.

@mdempsky
Copy link
Member Author

Here's a minimized, standalone repro of the nounified failure:

package http

func readTransfer(r *bufioReader) any {
	return NewChunkedReader(r)
}

func NewChunkedReader(r any) any {
	br, ok := r.(*bufioReader)
	if !ok {
		br = new(bufioReader)
		reset(br, r)
	}
	return &chunkedReader{r: br}
}

type chunkedReader struct {
	r *bufioReader
}

type bufioReader struct {
	rd any
}

func reset(b *bufioReader, r any) {
	b.rd = r
}

Compiled with -d=pctab=pctoinline, this input produces:

-- inlining tree for command-line-arguments.readTransfer:
0 | -1 | command-line-arguments.NewChunkedReader (/home/mdempsky/wd/go/src/net/http/dummy.go:8:25) pc=25
1 | 0 | command-line-arguments.reset (/home/mdempsky/wd/go/src/net/http/dummy.go:15:8) pc=0
--

Again, note the bad pc=0 value.

@mdempsky
Copy link
Member Author

Notably, the minimized test case repros with unified IR too, whereas the original net/http code did not.

@gopherbot
Copy link

Change https://go.dev/cl/425395 mentions this issue: cmd/compile/internal/noder: fix inlined function literal positions

@mdempsky
Copy link
Member Author

Looking at GOSSAFUNC=readTransfer output, the issue with the corrupt inline tree above is that the OpInlMark for the inlined reset call gets removed, because it's determined to be dead code. But when we spill AX to the stack, we end up using the position information from the inlined b.rd = r assignment.

This seems to be an issue with the "expand calls" phase. The inserted OpArgIntReg value seems to be taking the position of its first use, rather than the position of the original OpArg.

/cc @dr2chase

@cuonglm
Copy link
Member

cuonglm commented Aug 25, 2022

@mdempsky
Copy link
Member Author

@cuonglm Thanks, that seems plausible.

Further minimized repro:

package http

func readTransfer(r *int) {
	NewChunkedReader(r)
}

func NewChunkedReader(r *int) {
	if _, ok := any(r).(*int); !ok {
		// dead code path, but only recognized as such after "decompose builtins"
		reset(r)
	}
	sink = new(int) // force r to be spilled
	sink = r
}

func reset(r *int) {
	sink = r // anything that uses r
}

var sink any

@gopherbot
Copy link

Change https://go.dev/cl/425415 mentions this issue: cmd/internal/obj: report corrupt inline tree entries

@mdempsky
Copy link
Member Author

CL 425415 adds a hacky check that we find valid PC offsets for all of the inline tree entries we emit. In particular, it reports the miscompilation of the test case above.

@cuonglm
Copy link
Member

cuonglm commented Aug 25, 2022

With this patch, above test case pass, ./make.bash run ok:

diff --git a/src/cmd/compile/internal/ssa/expand_calls.go b/src/cmd/compile/internal/ssa/expand_calls.go
index 90ea2d5040..d1a742c014 100644
--- a/src/cmd/compile/internal/ssa/expand_calls.go
+++ b/src/cmd/compile/internal/ssa/expand_calls.go
@@ -1773,7 +1773,7 @@ func (x *expandState) newArgToMemOrRegs(baseArg, toReplace *Value, offset int64,
                toReplace.Type = t
                w = toReplace
        } else {
-               w = baseArg.Block.NewValue0IA(pos, op, t, auxInt, aux)
+               w = baseArg.Block.NewValue0IA(aux.Name.Pos(), op, t, auxInt, aux)
        }
        x.commonArgs[key] = w
        if toReplace != nil {

But still fails for some tests:

# go run run.go -- fixedbugs/issue53982.go
exit status 2
# command-line-arguments
<autogenerated>:1: inline marker #0 still poisoned

FAIL	fixedbugs/issue53982.go	0.131s
# go run run.go -- typeparam/issue47775.go
exit status 1
/home/cuonglm/sources/go/test/typeparam/issue47775.dir/b.go:13:6: inline marker #0 still poisoned

FAIL	typeparam/issue47775.go	0.105s
# go run run.go -- typeparam/issue47775b.go
exit status 1
/home/cuonglm/sources/go/test/typeparam/issue47775b.go:21:5: inline marker #0 still poisoned

FAIL	typeparam/issue47775b.go	0.052s
# go run run.go -- typeparam/issue49432.go
exit status 1
/home/cuonglm/sources/go/test/typeparam/issue49432.go:13:6: inline marker #0 still poisoned

FAIL	typeparam/issue49432.go	0.058s
exit status 1

Sounds like we still mess the pos somewhere else.

gopherbot pushed a commit that referenced this issue Aug 25, 2022
When inlining function calls, we rewrite the position information on
all of the nodes to keep track of the inlining context. This is
necessary so that at runtime, we can synthesize additional stack
frames so that the inlining is transparent to the user.

However, for function literals, we *don't* want to apply this
rewriting to the underlying function. Because within the function
literal (when it's not itself inlined), the inlining context (if any)
will have already be available at the caller PC instead.

Unified IR was already getting this right in the case of user-written
statements within the function literal, which is what the unit test
for #46234 tested. However, it was still using inline-adjusted
positions for the function declaration and its parameters, which
occasionally end up getting used for generated code (e.g., loading
captured values from the closure record).

I've manually verified that this fixes the hang in
https://go.dev/play/p/avQ0qgRzOgt, and spot-checked the
-d=pctab=pctoinline output for kube-apiserver and kubelet and they
seem better.

However, I'm still working on a more robust test for this (hence
"Updates" not "Fixes") and internal assertions to verify that we're
emitting correct inline trees. In particular, there are still other
cases (even in the non-unified frontend) where we're producing
corrupt (but at least acyclic) inline trees.

Updates #54625.

Change-Id: Iacfd2e1eb06ae8dc299c0679f377461d3d46c15a
Reviewed-on: https://go-review.googlesource.com/c/go/+/425395
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Auto-Submit: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
@gopherbot
Copy link

Change https://go.dev/cl/425785 mentions this issue: cmd/compile: fix wrong position when rewriting to OpArg/OpArgXXX

gopherbot pushed a commit that referenced this issue Aug 30, 2022
When spilling arg to stack or register, if it's a newly created value,
the arg position should be preserved. Otherwise, we may end up using
position information from deadcode lines.

This fixes the minimized test case in #54625 by mdempsky@, and make
building std successfully. However, the inline trees for these tests
still be corrupted:

 - fixedbugs/issue53982.go
 - typeparam/issue47775.go
 - typeparam/issue47775b.go
 - typeparam/issue49432.go

We probably still mess up the inline position somewhere else.

Updates #54625

Change-Id: I0d87e26b9ab451b85b6e79787da74a2b79a16209
Reviewed-on: https://go-review.googlesource.com/c/go/+/425785
Reviewed-by: David Chase <drchase@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Heschi Kreinick <heschi@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
rajbarik pushed a commit to rajbarik/go that referenced this issue Sep 1, 2022
When inlining function calls, we rewrite the position information on
all of the nodes to keep track of the inlining context. This is
necessary so that at runtime, we can synthesize additional stack
frames so that the inlining is transparent to the user.

However, for function literals, we *don't* want to apply this
rewriting to the underlying function. Because within the function
literal (when it's not itself inlined), the inlining context (if any)
will have already be available at the caller PC instead.

Unified IR was already getting this right in the case of user-written
statements within the function literal, which is what the unit test
for golang#46234 tested. However, it was still using inline-adjusted
positions for the function declaration and its parameters, which
occasionally end up getting used for generated code (e.g., loading
captured values from the closure record).

I've manually verified that this fixes the hang in
https://go.dev/play/p/avQ0qgRzOgt, and spot-checked the
-d=pctab=pctoinline output for kube-apiserver and kubelet and they
seem better.

However, I'm still working on a more robust test for this (hence
"Updates" not "Fixes") and internal assertions to verify that we're
emitting correct inline trees. In particular, there are still other
cases (even in the non-unified frontend) where we're producing
corrupt (but at least acyclic) inline trees.

Updates golang#54625.

Change-Id: Iacfd2e1eb06ae8dc299c0679f377461d3d46c15a
Reviewed-on: https://go-review.googlesource.com/c/go/+/425395
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Auto-Submit: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
@aclements
Copy link
Member

What's the status of this? I see the CL was merged. Should we rebase and re-trybot CL 425415 to see if it reports any other failures?

@cuonglm
Copy link
Member

cuonglm commented Jan 10, 2023

What's the status of this? I see the CL was merged. Should we rebase and re-trybot CL 425415 to see if it reports any other failures?

See my comment in #54625 (comment)

Those tests still failed with current tip.

@mdempsky mdempsky changed the title cmd/compile: unified IR is producing bad inlining trees for function literals cmd/compile: OpInlMark can get removed by SSA dead code elimination, resulting in invalid inlining trees Jan 10, 2023
@mdempsky
Copy link
Member Author

Should we rebase and re-trybot CL 425415 to see if it reports any other failures?

Done. Still reporting failures: https://storage.googleapis.com/go-build-log/eeb08b68/linux-amd64_bc78596a.log

Retitled to better reflect the current understanding of the issue, and bumping to 1.21.

@gopherbot
Copy link

Change https://go.dev/cl/468415 mentions this issue: cmd/compile/internal/noder: correct positions for synthetic closures

@mdempsky
Copy link
Member Author

@cuonglm points out that CL 468415 addresses the failures reported by CL 425415. So I'll look into polishing that CL up to mail out for inclusion, at least during the dev cycle to help smoke out more failure cases.

I think the underlying issue around ssa's deadcode elimination pass and OpInlMarks is still applicable though.

gopherbot pushed a commit that referenced this issue Feb 27, 2023
When inlining functions that contain function literals, we need to be
careful about position information. The OCLOSURE node should use the
inline-adjusted position, but the ODCLFUNC and its body should use the
original positions.

However, the same problem can arise with certain generic constructs,
which require the compiler to synthesize function literals to insert
dictionary arguments.

go.dev/cl/425395 fixed the issue with user-written function literals
in a somewhat kludgy way; this CL extends the same solution to
synthetic function literals.

This is all quite subtle and the solutions aren't terribly robust, so
longer term it's probably desirable to revisit how we track inlining
context for positions. But for now, this seems to be the least bad
solution, esp. for backporting to 1.20.

Updates #54625.
Fixes #58513.

Change-Id: Icc43a70dbb11a0e665cbc9e6a64ef274ad8253d1
Reviewed-on: https://go-review.googlesource.com/c/go/+/468415
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
@gopherbot
Copy link

Change https://go.dev/cl/471677 mentions this issue: [release-branch.go1.20] cmd/compile/internal/noder: correct positions for synthetic closures

gopherbot pushed a commit that referenced this issue Feb 28, 2023
… for synthetic closures

When inlining functions that contain function literals, we need to be
careful about position information. The OCLOSURE node should use the
inline-adjusted position, but the ODCLFUNC and its body should use the
original positions.

However, the same problem can arise with certain generic constructs,
which require the compiler to synthesize function literals to insert
dictionary arguments.

go.dev/cl/425395 fixed the issue with user-written function literals
in a somewhat kludgy way; this CL extends the same solution to
synthetic function literals.

This is all quite subtle and the solutions aren't terribly robust, so
longer term it's probably desirable to revisit how we track inlining
context for positions. But for now, this seems to be the least bad
solution, esp. for backporting to 1.20.

Updates #54625.
Fixes #58531.

Change-Id: Icc43a70dbb11a0e665cbc9e6a64ef274ad8253d1
Reviewed-on: https://go-review.googlesource.com/c/go/+/468415
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
(cherry picked from commit 873c14cec730ee278848f7cc58d2b4d89ab52288)
Reviewed-on: https://go-review.googlesource.com/c/go/+/471677
Auto-Submit: Dmitri Shuralyov <dmitshur@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
romaindoumenc pushed a commit to TroutSoftware/go that referenced this issue Mar 3, 2023
… for synthetic closures

When inlining functions that contain function literals, we need to be
careful about position information. The OCLOSURE node should use the
inline-adjusted position, but the ODCLFUNC and its body should use the
original positions.

However, the same problem can arise with certain generic constructs,
which require the compiler to synthesize function literals to insert
dictionary arguments.

go.dev/cl/425395 fixed the issue with user-written function literals
in a somewhat kludgy way; this CL extends the same solution to
synthetic function literals.

This is all quite subtle and the solutions aren't terribly robust, so
longer term it's probably desirable to revisit how we track inlining
context for positions. But for now, this seems to be the least bad
solution, esp. for backporting to 1.20.

Updates golang#54625.
Fixes golang#58531.

Change-Id: Icc43a70dbb11a0e665cbc9e6a64ef274ad8253d1
Reviewed-on: https://go-review.googlesource.com/c/go/+/468415
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
(cherry picked from commit 873c14cec730ee278848f7cc58d2b4d89ab52288)
Reviewed-on: https://go-review.googlesource.com/c/go/+/471677
Auto-Submit: Dmitri Shuralyov <dmitshur@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
@mknyszek
Copy link
Contributor

mknyszek commented Jun 9, 2023

Hey @mdempsky, doing a sweep of the Go 1.21 milestone. Any updates here?

Pushing to Backlog for now, feel free to move it to the Go 1.22 milestone if you plan to work on it. Thanks!

@mknyszek mknyszek modified the milestones: Go1.21, Backlog Jun 9, 2023
@mdempsky mdempsky removed their assignment Nov 19, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. help wanted NeedsFix The path to resolution is known, but the work has not been done.
Projects
Status: In Progress
Development

No branches or pull requests

5 participants