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.

Sign up for GitHub

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

Jump to bottom

cmd/compile: record which instructions clobber flags #12054

Closed
josharian opened this issue Aug 6, 2015 · 4 comments
Closed

cmd/compile: record which instructions clobber flags #12054

josharian opened this issue Aug 6, 2015 · 4 comments
Labels
FrozenDueToAge
Milestone
Go1.6

Comments

@josharian
Copy link
Contributor

This code is currently miscompiled:

package main

func f_ssa(r int64, n uint) int64 {
    switch { // prevent inlining
    }
    x := (r << n) >> n
    return x
}

func main() {
    println(f_ssa(97, 32))
}

With tip, it correctly prints 97. With SSA, it prints 0. I found this because it caused the fmt package tests to fail.

Diagnosis:

Just before lowering, the SSA looks good:

  b2:
    v1 = Arg <mem>
    v2 = SP <uintptr>
    v4 = Addr <*int64> {r} v2
    v5 = Addr <*uint> {n} v2
    v6 = Addr <*int64> {~r2} v2
    v10 = Zero <mem> [8] v6 v1
    v19 = Load <int64> v4 v1
    v21 = Load <uint> v5 v1
    v13 = Lsh64x64 <int64> v19 v21
    v14 = Rsh64x64 <int64> v13 v21
    v16 = Store <mem> v6 v14 v10
    Exit v16

The lowered form is fine:

  b2:
    v1 = Arg <mem>
    v2 = SP <uintptr>
    v4 = LEAQ <*int64> {r} v2
    v5 = LEAQ <*uint> {n} v2
    v6 = LEAQ <*int64> {~r2} v2
    v19 = MOVQload <int64> {r} v2 v1
    v21 = MOVQload <uint> {n} v2 v1
    v15 = SHLQ <int64> v19 v21
    v11 = CMPQconst <flags> [64] v21
    v9 = CMPQconst <flags> [64] v21
    v8 = MOVQconst <int64>
    v10 = MOVQstore <mem> {~r2} v2 v8 v1
    v12 = SBBQcarrymask <int64> v11
    v18 = SBBQcarrymask <uint> v9
    v13 = ANDQ <int64> v15 v12
    v20 = NOTQ <uint> v18
    v17 = ORQ <uint> v21 v20
    v14 = SARQ <int64> v13 v17
    v16 = MOVQstore <mem> {~r2} v2 v14 v10
    Exit v16

However, lowered cse combines the two CMPQconst values (v11, v9), but not the two SBBQcarrymask instructions that use them (v12, v18), because they have different types.

As a result, the CMP occurs only once, but the first SBBQ clobbers the flags, making the second SBBQ wrong. We need to find all instructions that clobber flags, mark them as such, and teach the register allocator both about clobbering and about how to save/restore flags.

For completeness, just before codegen, the function reads:

  b2:
    v2 = SP <uintptr> : SP
    v1 = Arg <mem>
    v9 = MOVQload <int64> {r} v2 v1 : AX
    v6 = MOVQload <uint> {n} v2 v1 : CX
    v5 = SHLQ <int64> v9 v6 : DX
    v4 = CMPQconst <flags> [64] v6 : FLAGS
    v7 = SBBQcarrymask <int64> v4 : BX
    v3 = ANDQ <int64> v5 v7 : BP
    v22 = SBBQcarrymask <uint> v4 : SI
    v23 = NOTQ <uint> v22 : DI
    v24 = ORQ <uint> v6 v23 : R8
    v25 = Copy <uint> v24 : CX
    v26 = SARQ <int64> v3 v25 : R9
    v27 = MOVQconst <int64> : R10
    v10 = MOVQstore <mem> {~r2} v2 v27 v1
    v16 = MOVQstore <mem> {~r2} v2 v26 v10
    Exit v16

And the generated assembly is:

    00000 (x.go:3)  TEXT    "".f_ssa(SB), $0-24
    00001 (x.go:3)  FUNCDATA    $0, "".gcargs·0(SB)
    00002 (x.go:3)  FUNCDATA    $1, "".gclocals·1(SB)
    00003 (x.go:3)  TYPE    "".r(FP), $8
    00004 (x.go:3)  TYPE    "".n+8(FP), $8
    00005 (x.go:3)  TYPE    "".~r2+16(FP), $8
    00006 (x.go:3)  TYPE    "".x(SP), $8
v9  00007 (x.go:3)  MOVQ    8(SP), AX
v6  00008 (x.go:3)  MOVQ    16(SP), CX
v5  00009 (x.go:7)  MOVQ    AX, DX
v5  00010 (x.go:7)  SHLQ    CX, DX
v4  00011 (x.go:7)  CMPQ    CX, $64
v7  00012 (x.go:7)  SBBQ    BX, BX
v3  00013 (x.go:7)  MOVQ    DX, BP
v3  00014 (x.go:7)  ANDQ    BX, BP
v22 00015 (x.go:7)  SBBQ    SI, SI
v23 00016 (x.go:7)  MOVQ    SI, DI
v23 00017 (x.go:7)  NOTQ    DI
v24 00018 (x.go:7)  MOVQ    CX, R8
v24 00019 (x.go:7)  ORQ DI, R8
v25 00020 (x.go:7)  MOVQ    R8, CX
v26 00021 (x.go:7)  MOVQ    BP, R9
v26 00022 (x.go:7)  SARQ    CX, R9
v27 00023 (x.go:3)  MOVQ    $0, R10
v10 00024 (x.go:3)  MOVQ    R10, 24(SP)
v16 00025 (x.go:10) MOVQ    R9, 24(SP)
b2  00026 (x.go:3)  RET
    00027 (<unknown line number>)   RET

The value v22 (instruction 15) is wrong.

/cc @randall77
@josharian josharian added this to the Go1.6 milestone Aug 6, 2015
@randall77
Copy link
Contributor

Yes, we have to add flags clobbering to (almost) everything. And flags spill/restore.

It might be worth changing the type of the SBBQs to match so they get CSEd. I'll leave it for now though, so we have an obvious test case for this issue.

@josharian
Copy link
Contributor Author

Agreed--I think that systematically stripping a bunch of type distinctions would make lowered CSE much more effective.

@gopherbot
Copy link

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

@randall77
Copy link
Contributor

Fixed with https://go-review.googlesource.com/#/c/13622/

@golang golang locked and limited conversation to collaborators Aug 22, 2016
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.6
Development

No branches or pull requests
3 participants
@josharian @randall77 @gopherbot