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: bug in spill sinking #20472

Closed
cherrymui opened this issue May 23, 2017 · 6 comments

Comments

Projects
None yet
5 participants
@cherrymui
Copy link
Contributor

commented May 23, 2017

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

go version go1.8 darwin/amd64

building code for PPC64LE.

package main

import (
        "fmt"
)

type S struct {
        A, B int64
}

type T struct {
        ss []S
}

func (t *T) F(s S) {
        n := len(t.ss) - 1
        for ; n >= 0; n-- {
                if t.ss[n].A < s.B {
                        fmt.Println(s, n, t.ss[n])
                        panic("A")
                }

                if t.ss[n-1].B == s.A && s.B == t.ss[n].A {
                        t.ss = append(t.ss[0:n-1],
                                append([]S{S{A: t.ss[n-1].A, B: t.ss[n].B}},
                                        t.ss[n+1:len(t.ss)]...)...)
                        return
                }
        }
        panic("XXX")
}

func main() {
        t := &T{ss: []S{{1, 4}, {7, 8}}}
        fmt.Println(t)
        t.F(S{4, 7})
        fmt.Println(t) // should be &{[{1 8}]}
}

Building this program on PPC64LE with Go 1.8, the result's len is wrong, so it prints something like &{[{1 8} {7 8} {842350502368 2} {2 0} {9021871350425025318 9033514107587230496} {10 0} {0 0} {0 0} {0 0} {0 0} {0 0} {0 0} {0 0} {0 0} {0 0} {0 0} {0 0}]}
instead of &{[{1 8}]}, which it prints on AMD64.

On tip, it produces the right result.

Look at ssa.html, before regalloc (looking at flagalloc column), we have v311 = ADD <int> v135 v261 in b35. After regalloc, it becomes
v311 = ADD <int> v33 v401 : R5 (in b35), where
v33 = LoadReg <int> v364 : R3 (in b35),
v364 = StoreReg <int> v135 : .autotmp_31[int] (in b7), which is the spill of v135.
However, in b21, there is also v403 = StoreReg <int> v395 : .autotmp_31[int] which is on the code path, and clobbers the stack slot.

The bad spill (v403) is originally generated in b8, and the spill sinking code moves it to b21, which is problematic. If spill sinking is disabled, it runs fine.

The bug does not exist on tip, as @randall77 rewrote the spill placement code. But we probably need to fix Go 1.8.

@cherrymui cherrymui added this to the Go1.8.3 milestone May 23, 2017

@cherrymui

This comment has been minimized.

Copy link
Contributor Author

commented May 23, 2017

It seems I cannot attach html file... zipped...

ssa.html.zip

@bradfitz

This comment has been minimized.

Copy link
Member

commented May 23, 2017

We're rolling Go 1.8.3 as we speak. Do we need to wait on 1.8.3 or can this wait until a Go 1.8.4?

@cherrymui

This comment has been minimized.

Copy link
Contributor Author

commented May 23, 2017

I'm not sure. I'm still looking into it, trying to understand why it goes wrong and how simple the fix could be.

@randall77

This comment has been minimized.

Copy link
Contributor

commented May 23, 2017

I think I see what is going wrong.
In the loop in question, we have a spill v403 = StoreReg v395

To decide whether we need to move/copy the spill v403 to an exit, we need to know whether the value is live at that exit. Unfortunately, we conflate uses of v403 with uses of v395. At the exit in question, v395 is live but v403 isn't. So we move the spill v403 to that exit, even though it isn't needed there. Even worse, spill location assigned to v403 is by this point used by another spill.

I think we just have to be more careful about only using the spilled value when computing liveness, not the orig[] of that value. I'll see if I can whip up a CL tonight.

@gopherbot

This comment has been minimized.

Copy link

commented May 24, 2017

CL https://golang.org/cl/44033 mentions this issue.

@bradfitz

This comment has been minimized.

Copy link
Member

commented May 24, 2017

A test for tip would be nice too.

gopherbot pushed a commit that referenced this issue May 24, 2017

[release-branch.go1.8] cmd/compile: don't move spills to loop exits w…
…here the spill is dead

We shouldn't move a spill to a loop exit where the spill itself
is dead.  The stack location assigned to the spill might already
be reused by another spill at this point.

The case we previously handled incorrectly is the one where the value
being spilled is still live, but the spill itself is dead.

Fixes #20472

Patching directly on the release branch because the spill moving code has
already been rewritten for 1.9. (And it doesn't have this bug.)

Change-Id: I26c5273dafd98d66ec448750073c2b354ef89ad6
Reviewed-on: https://go-review.googlesource.com/44033
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

@broady broady closed this May 24, 2017

gopherbot pushed a commit that referenced this issue May 24, 2017

cmd/compile: test for moving spills
Test that we really do move spills down to the dominator of
all the uses.

Also add a test where go1.8 would have moved the spill out of
the loop into two exit points, but go1.9 doesn't move the spill.
This is a case where the 1.9 spill moving code does not subsume
the 1.8 spill moving code.

Maybe we resurrect moving-spills-out-of-loops CL to fix this one.
(I suspect it wouldn't be worth the effort, but would be happy
to hear evidence otherwise.)

Update #20472

Change-Id: I7dbf8d65e7f4d675d14e5ecf502887cebda35d2a
Reviewed-on: https://go-review.googlesource.com/44038
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>

@golang golang locked and limited conversation to collaborators May 24, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.